Сергей Хрущев вспоминал: «Еще в день приезда президент Насер объявил о награждении отца орденом Ожерелье Нила, которым отмечали за особые заслуги, и то чрезвычайно редко… Возникла проблема: каким советским орденом можно наградить президента Насера и командующего вооруженными силами маршала Мухаммеда Амера… Отец, долго не раздумывая, принял представление о присвоении звания Героя Советского Союза президенту Насеру и – по предложению маршала Гречко – маршалу Амеру… В Москву ушла соответствующая шифровка, и вскоре был получен положительный ответ в виде Указа Президиума Верховного Совета СССР за подписью Брежнева. Привезли и запечатанный сургучными печатями сверток с наградами. В торжественной обстановке отец вручал ордена Насеру и Амеру». Из этого рассказа следует, что решение о наградах Насера и Амера решалось лишь после прибытия Хрущева в Египет.

Шелепин же утверждал, что до отъезда Хрущева в Египет Президиум ЦК принял решение наградить Насера орденом «Дружбы народов», но Хрущев нарушил это решение. Хрущев, очевидно, не понимал отношения советских людей к званию Героя Советского Союза. Считалось, что такого звания заслуживают лишь люди, проявившие чудеса героизма в мирной жизни или совершившие воинский подвиг в боях за Родину. Первыми Героями Советского Союза были летчики, спасавшие с риском для жизни участников экспедиции «Челюскина», пилоты, впервые перелетевшие через Северный полюс. Затем героями стали мужественные воины Великой Отечественной войны, сражавшиеся под Сталинградом, форсировавшие Днепр, штурмовавшие Берлин, партизаны «Молодой Гвардии» и Зоя Космодемьянская, Александр Матросов и Николай Гастелло, космонавты СССР. Как известно, И.В. Сталин наотрез отказался принять это звание после того, как оно было ему присвоено в июне 1945 года. Он возмущался: «Я не ходил в атаку с винтовкой наперевес!»

Как указывалось ранее, первым руководителем зарубежной страны, которому было присвоено звание Героя Советского Союза, стал Фидель Кастро. Награждение популярного Фиделя приветствовали в СССР. Во-первых, потому что он, руководитель и участник штурма крепости Монкады и победоносного народного восстания против коррумпированного диктатора, был олицетворением революционного героизма, в духе которого были воспитаны несколько поколений советских людей. Во-вторых, потому что в трудные дни Карибского кризиса Фидель Кастро олицетворял героизм кубинцев, стоявших рядом с советскими воинами.

Однако поскольку президент Алжира Бен Белла также олицетворял революционный героизм своего народа, Хрущев присвоил и ему звание Героя Советского Союза. Вероятно, это было лишним. Во-первых, в отличие от Кубы, Алжир не был столь близок к СССР. Сотрудничество Алжира и СССР не прошло через горнило таких испытаний, через какие прошла кубино-советская дружба. Во-вторых, о Бен Белле было мало известно в СССР и он не казался личностью, заслуживающей звания «Героя», а уж тем более «Советского Союза». Но, присвоив Бен Белле звание Героя Советского Союза, Хрущев создал опасный прецедент. Теперь любой лидер стран Азии, Африки и Латинской Америки, объявлявший себя революционером, мог претендовать на звание Героя Советского Союза. Хотя подавляющее большинство советских людей, кроме ярых поклонников Израиля, не испытывало неприязни ни к Насеру, ни к Амеру, их возмущение награждением двух руководителей Египта золотыми звездами Героя Советского Союза было велико и лишь усилило недовольство Хрущевым.

Во время пребывания в Египте Хрущев принял участие в торжественном пуске Асуанской плотины, построенной на советские средства и с помощью советских специалистов. Помимо Хрущева и Насера в церемонии пуска плотины приняли участие президент Алжира Бен Белла, президент Йемена Ас-Саляль и президент Ирака Ареф. Последний пришел к власти в феврале 1963 года в результате военного переворота, в ходе которого был убит руководитель Ирака Абдель Касем и расстреляны тысячи коммунистов во главе с Салямом Адилем. В СССР с возмущением реагировали на переворот Арефа, а одну из московских улиц назвали именем Саляма Адиля. Теперь Хрущев вынужден был вместе с Арефом нажимать кнопку пуска плотины, построенной Советским Союзом. После выступления Арефа на митинге по случаю пуска плотины, в котором тот подчеркивал необходимость сплочения всех арабов, выступил Хрущев. Он говорил о том, что арабы бывают разные: есть арабы – рабочие, а есть – капиталисты. «О каких арабах говорите вы? О рабочих арабах или арабских капиталистах?» – спрашивал Хрущев Арефа. После выступления Хрущева к нему подошел Насер и стал объяснять ему, что Ареф – сторонник единства арабских стран и Египет будет поддерживать Арефа.

Впрочем, Хрущеву понравились рассуждения Арефа об арабском социализме. Еще больше ему понравились подобные высказывания Насера. Он пришел к выводу, что Насер строит в Египте социалистическое общество, и решил помочь ему в этом. Своим волевым решением Хрущев в ходе переговоров с президентом Египта Насером сократил египетский долг наполовину (на 2,5 миллиарда долларов). В отчете о своей поездке на заседании Президиума ЦК 26 мая Хрущев расхваливал ее итоги. Аджубей добавлял: «В сложной обстановке диалектическое мышление Никиты Сергеевича схватывало суть, зерно существенного».

Тем временем Хрущев снова стал готовиться к зарубежной поездке, на сей раз в Скандинавские страны, которая начиналась 15 июня. По подсчетам Таубмэна, Хрущев в 1963 году в течение 170 дней был вне Москвы в СССР или заграницей, а за первые 9 месяцев 1964 года он 150 дней находился за пределами Москвы. Пребывание Хрущева и его многочисленных помощников вне Москвы лишь облегчало подготовку заговора против него.

Сергей Хрущев утверждает, что еще до начала поездки его отца в Египет была заметна «непонятная перемена в поведении Леонида Ильича. Его всегда отличала широкая располагающая улыбка, готовая сорваться с языка шутка. На сей раз он был мрачен, даже отцу отвечал односложно, почти грубо». С.Н. Хрущев объяснял эту перемену решением освободить Л.И. Брежнева от обязанностей Председателя Президиума Верховного Совета СССР на июльской сессии Верховного Совета. Утверждалось, что Л.И. Брежневу очень нравилась эта должность, связанная с официальными церемониями, вручениями верительных грамот послов и правительственных наград, государственными визитами глав зарубежных стран и визитами в эти страны. В июле 1964 года этот пост занял А.И. Микоян. Позже Сергей Хрущев писал: «Только в последнее время, когда стали известны многие обстоятельства тех лет, все стало выглядеть в ином свете. Очевидно, к маю окончательно оформилось решение избавиться от Хрущева. Оставалось, видимо, продумать детали и возможные сроки. Тогда, в Ялте, Брежнев, вероятно, не смог скрыть своего истинного отношения к отцу».

Тем временем, по словам Семичастного, «круг посвященных постепенно разрастался, однако все еще не существовало конкретного плана и единой стратегии действий. Вопросы, что делать, а главное – как дальше действовать, не выходили целыми днями из головы Брежнева… Однажды он снова мне позвонил и попросил зайти: хочет, мол, обсудить один практический вопрос. Вскоре я был в его кабинете. В это время Хрущев собирался выехать в Швецию и, как уже стало традицией, намеревался ехать туда всей семьей – сначала на поезде до Ленинграда, а оттуда на корабле по морю. Предложение Брежнева звучало весьма ясно: "Что если бы КГБ задержал поезд Хрущева при его возвращении из Ленинграда где-нибудь у Завидова и изолировал Первого секретаря?" Семичастный замечал: "При таком варианте вступление в должность нового «Первого» прошло бы в обстановке полной безопасности". Разумеется, в то время Леонид Ильич, будучи вторым секретарем ЦК КПСС, уже понял, что тем новым, кто заменит Хрущева, будет именно он. Однако он хорошо расценивал и свои возможности, а потому по мере приближения решающего момента его страх перед Никитой Сергеевичем нарастал. Предложение Брежнева меня неприятно удивило. Даже если бы в конце концов группа Президиума остановилась именно на таком варианте (в чем я вовсе не был уверен), наши действия были бы совершенно противозаконными и вызвали осуждение во всем мире».