С воздуха их сопровождала стратегическая и морская авиация, взлетавшая с баз сначала на Кольском полуострове и в Египте, а затем, по мере приближения с юга к Европе – и с баз в Югославии. Над соединением висели дирижабли ДРЛО, заправлявшиеся и обслуживаемые с трофейных авианосцев, на которые был погружен запас топлива и запчастей.

Истребительное прикрытие организовали просто. Африка в конце 1956 года была конгломератом колониальных владений Англии, Франции, Бельгии и Португалии. Колониальная администрация славилась своей неповоротливостью. Поселения европейцев группировались на побережье и в районах добычи полезных ископаемых, тогда как внутри континента жили лишь местные племена. К тому же было известно, что в Африке, кроме Сахары, в основном твёрдые грунты, какая-либо ПВО отсутствует, а истребители МиГ-17 прекрасно чувствовали себя на грунтовых аэродромах.

Исходя из этого, Жигарев предложил послать для прикрытия флота истребительную авиадивизию, из числа самолётов, базировавшихся в Египте, организуя аэродромы подскока для истребителей прямо в африканской саванне. Снабжение топливом организовали с дирижаблей, топливо они брали с танкеров, сопровождавших отряд кораблей. Истребители перелетали с одного импровизированного аэродрома на другой вдоль побережья. Аэродромы организовывали вдали от поселений европейцев, в дикой, малонаселённой местности, местных вождей племён при необходимости подкупали, а по большей части – просто поили водкой.

Расчёт по дальности каждого отдельного перелёта показал, что по всему побережью сопровождение организовать будет сложно, разве что с подвесными баками. Особую проблему представляла Экваториальная Африка – сесть в саванне МиГи могли, а вот в джунглях... Однако к вопросу подключился лично Хрущёв. Используя свои хорошие отношения с королевой Бельгии Елизаветой, он договорился через неё, в обход бельгийского правительства, о посадке истребителей для дозаправки на аэродроме в Бельгийском Конго. Взятки, сунутые агентурой ГРУ нескольким колониальным чиновникам, довершили дело. О дозаправке советских истребителей в Конго бельгийский премьер узнал, лишь когда самолётов там уже не было.

Основными пунктами базирования стали Ангола, Мали и Мавритания. Место для посадки сначала проверялось инженерным десантом, высаженным с дирижабля. Если площадка была ровная и с достаточно твёрдым грунтом, на ней расставляли радиомаяки, выкладывали полотнища для разметки, вставшие на якоря дирижабли выгружали дозаправочное оборудование. В Мавритании были даже построены временные аэродромы из выложенных поверх песчаного грунта стальных листов.

Самолёты садились, заправлялись, при необходимости заменялись изношенные запчасти, вплоть до двигателей, после чего они снова летели на патрулирование.

Встреча флотов произошла в Гвинейском заливе. При этом прикрывающие флот истребители были сменены другой дивизией, временно развёрнутой в малонаселённых районах Мали.

Здесь же была проведена ротация сил Средиземноморской эскадры СССР (АИ). По указанию Хрущёва ни один из имевшихся на тот момент крупных кораблей не был разоружён или списан, даже совсем старые крейсеры проекта 26 ремонтировались и использовались.

Хрущёв надеялся в будущем переоснастить их электромагнитными пушками, но с их разработкой обнаружились серьёзные сложности, особенно с живучестью рельсов и энергетическим обеспечением. Потому было решено постепенно переоснащать старые корабли ракетным вооружением, при сохранении, где возможно, части артиллерии главного калибра, обновлении малокалиберной зенитной и универсальной артиллерии, а также установке перспективных ЗРК.

На 1 декабря 1956 г. в составе Средиземноморского флота СССР (АИ) был линкор «Новороссийск», крейсеры «Фрунзе», «Куйбышев», «Адмирал Нахимов», «Ворошилов» и «Молотов» «Михаил Кутузов», «Дзержинский», а также эсминцы, подводные лодки, минные заградители, торпедные катера. В результате ротации на ЧФ вернулись крейсеры «Адмирал Нахимов» и «Дзержинский», на которых проводилась отработка комплексов ПКР и ЗРК, «Ворошилов» и «Молотов». С Балтийского флота на Средиземное были переведены крейсеры «Орджоникидзе» и «Жданов», уже оснащённые комплексом КСС, как и «Адмирал Нахимов».(АИ) С Северного флота пришли крейсеры «Адмирал Лазарев» и «Александр Невский». Они также получили комплексы КСС и усиленную зенитную артиллерию. (АИ) Это была полумера, но всё лучше, чем ничего. Помимо них, в составе флота были собранные с других флотов подводные лодки, минные заградители, тральщики, торпедные катера, вспомогательные корабли.

Флагманом Средиземноморского флота был линкор «Новороссийск». С ноября 1956 года в его боекомплекте произошли существенные изменения – из Советского Союза были доставлены активно-реактивные снаряды с обычным и ядерным снаряжением. Обычные использовались, по большей части для тренировок. Попасть в цель на дистанции в 100 километров было маловероятно, а самонаводящиеся АРС ещё разрабатывались.

От побережья Западной Африки трофеи пошли под охраной кораблей Северного и Балтийского флотов, а также четырёх крейсеров, и линкора «Новороссийск», которым предстояло вернуться в Средиземное. Флагманом Объединённого флота был линкор «Октябрьская Революция» под флагом адмирала Горшкова.

На траверзе Сенегала флот впервые был обнаружен американской палубной авиацией – до этого большую часть пути прошли спокойно, все встреченные суда были торговыми. Но здесь к прикрытию добавились Ту-95 и Ту-16 морской авиации, взлетавшие из Югославии и проходившие над международными водами, а иногда – и внаглую над малонаселёнными районами Марокко.

Висящие над соединением, сменяющие друг друга истребители сбили первоначальную наглость с американцев. Их патрульные самолёты следили за флотом издалека, не приближаясь. По радиоперехватам было ясно, что американцы крайне озадачены присутствием советских истребителей в столь отдалённом районе.