В июле 1956 года Насер национализировал Суэцкий канал, который был в свое время отдан в концессию обосновавшейся в Париже Компании Суэцкого канала и в глазах арабов был самым ярким символом западной эксплуатации. После того, как в ноябре Англия и Франция в сговоре с Израилем неудачно попытались восстановить контроль над Суэцким каналом с помощью оружия, Насер стал героем для большей части арабского мира (не признали его разве что только ортодоксальные арабские лидеры). В 1958 году Насер совершил трехнедельную поездку по Советскому Союзу, где его также чествовали как героя. Советское руководство в полном составе прибыло в аэропорт, чтобы встретить его, он был почетным гостем на трибуне Мавзолея во время ежегодной Первомайской демонстрации на Красной площади. По возвращении на родину Насер, выступая перед огромной толпой в Каире, сказал, что Советский Союз — «дружественная страна, не преследующая никаких корыстных интересов», которая питает к арабам «глубокое уважение».
Но не всегда отношения между Насером и Кремлем складывались гладко. Серьезные трения возникли после того, как Насер начал преследовать коммунистов в Египте и Сирии (в период союза между двумя странами с 1958 по 1961 год) и выступил с осуждением коммунистов в Ираке. КГБ было наверняка известно, что после того, как Насер публично выступил с критикой политики, проводимой Советским Союзом в 1959 году, ЦРУ предложило ему американскую помощь. Но, несмотря ни на что, в начале шестидесятых Хрущев и Центр были убеждены, что на Ближнем Востоке сложилось новое «соотношение сил», которое необходимо было использовать в борьбе с «главным противником», хотя и не все члены Политбюро разделяли эту точку зрения. Сирия и Ирак, а также Египет были настроены претив США. В 1962 году Бен Белла в Алжире провозгласил курс на построение социализма и ввел в состав правительства нескольких коммунистов. После пережитого во время Карибского кризиса унижения Хрущев укрепился в своей решимости одержать верх над США в борьбе за влияние на Ближнем Востоке. Победа Кастро на Кубе явилась еще одним свидетельством в пользу новой политики союза с антиимпериалистическими, хотя и идейно не совсем последовательными, националистами в третьем мире, вместо традиционной опоры на коммунистические партии старого толка, которые были готовы идти за Москвой по пятам.
Советские идеологи изобрели термины «некапиталистический путь» и «революционная демократия» для обозначения переходной стадии от капитализма к социализму. Именно к этой стадии тяготели некоторые лидеры третьего мира. Решение Насера о национализации большей части египетской промышленности в 1961 году стало обнадеживающим свидетельством его движения по «некапиталистическому пути». На протяжении шестидесятых годов Советский Союз возлагал на него больше надежд, чем на любого другого афро-азиатского лидера. В период с 1953 по 1971 год на Египет приходилось 43 процента всего объема советской помощи третьему миру. В 1965 году египетская компартия объявила о своем роспуске, и ее члены подали заявление о приеме в правящий Арабский Социалистический Союз.