Конституция, принятая в июне 1956 года, формально закрепила за Насером верховный пост и заложила основы новой государственной системы. Первый президент был избран общенациональным голосованием (впервые избирательное право предоставили женщинам): за Насера 23 июля проголосовали 99,9 % избирателей, а против — официально никто. Впоследствии право избирать президента перешло к заново созванному однопалатному Национальному собранию. Конституция предоставила президенту «право вносить, продлевать или накладывать вето на законодательный акт», подчеркивая приоритет исполнительной власти над законодательной; президент также возглавил «Национальный союз», новую политическую организацию, открытую для всех египтян и заменившую «Либеральное объединение». Из числа членов «Союза» Насер лично отбирал кандидатов для списка, по которому проводили выборы в Национальное собрание (350 мест).
Для решения двух самых насущных вопросов египетской политики — присутствия в стране британских войск и статуса Судана — у Насера было больше свободы, чем у любого другого государственного деятеля Египта с момента обретения независимости. Переговоры с Великобританией начались вскоре после революции. В феврале 1953 года было принято решение, что народ Судана после трехлетнего переходного периода самостоятельно выберет между союзом с Египтом и полной независимостью. Это означало, что проблема англо-египетского кондоминиума так или иначе урегулирована. К изумлению египтян, 1 января 1956 года Судан провозгласил независимость.
После двух лет трудных переговоров договор об эвакуации британских войск был подписан 19 октября 1954 года; он гарантировал вывод британской армии из Египта в течение двадцати месяцев. Военные объекты в зоне Суэцкого канала оставались в совместном владении еще на семь лет: британцы могли ввести войска в зону канала в случае внешней агрессии против любого из членов Арабской лиги или Турции — под внешней агрессией подразумевалась коммунистическая угроза. Далеко не всем понравилось это условие, но Насер, который вел переговоры, верил, что главное — организовать эвакуацию британцев. Когда договор был подписан, Насер сказал:
Последний британский солдат покинул Порт-Саид 13 июня 1956 года, на чем завершилась история 74-летней оккупации. К несчастью, менее чем через пять месяцев британские войска вернулись.
Уход британцев из Египта стал первой победой «Свободных офицеров» в глобальной борьбе против западного империализма. Насер видел Египет в роли естественного лидера движения сопротивления, поскольку страна занимала ключевое место в арабском мире — регионе, по его словам, имевшем «общие условия существования, общие проблемы, общее будущее и общего врага, какие бы маски тот ни надевал». Не все арабские страны разделяли воззрения Насера. Монархи Саудовской Аравии и Иордании с глубоким подозрением смотрели на молодых египетских революционеров, а премьер-министр Ирака Нури аль-Саид, глава государства, уступавшего только Египту, с точки зрения Насера был прислужником Запада.
Международные отношения усложнились в период «холодной войны». В попытке сдержать советскую экспансию, США заключили ряд оборонительных пактов. В 1955 году был подписан Багдадский пакт между Ираком и Турцией, их коалиция позволила создать центральное звено в цепочке НАТО — СЕАТО (блок стран Юго-Восточной Азии). Насер не одобрил эту коалицию, обвинял Нури в предательстве арабов и в том, что он играет на руку «империалистическому Западу»; слова Насера подтвердила Великобритания, присоединившаяся к пакту позднее в том же году (вместе с Ираном и Пакистаном), чтобы укрепить свое влияние в регионе.
Не понадобилось сверхусилий, чтобы сформировать оппозицию всего арабского мира Ираку и пакту: свою роль сыграли пламенные выступления по каирскому радио «Голос арабов» (это орудие пропаганды Насер широко использовал). Едкие нападки Насера производили сильное впечатление на арабов, а на Западе полковник быстро сделался одиозной фигурой.