13 июня 1962 года в Главный штаб ВМФ прибыла директива Генерального штаба № 79604 с указанием начать разработку морской части темы «Анадырь». Одновременно генерал армии Захаров распорядился выплатить всем участникам предстоящего похода на Кубу денежное содержание на три месяца вперед. Тем, кому предстояло идти на Кубу на борту гражданских судов, выдавалась гражданская одежда — отныне они становились агрономами и строителями, геологами и механизаторами. Для маскировки порта назначения было дано указание грузить валенки и полушубки, варежки и шапки-ушанки, причем все в количествах немыслимых. Глядя на эти горы зимней одежды, бдительные шпионы должны были делать вывод, что русские собираются оккупировать то ли Гренландию, то ли Антарктиду.
Секретность была жесточайшая во всем Легендировался каждый шаг. Распоряжения по теме «Анадырь» передавались только устно и шифром.
Для перевозки техники были заказаны специальные контейнеры, изготовление которых курировал лично предсовмина Косыгин. Контейнеры эти изнутри обивали железом, на случай, если американцам удастся проверять их содержимое рентгеновскими или инфракрасными лучами. К июлю все приготовления были закончены. Теперь ждали лишь сигнала к началу операции.
7 июля 1962 года в Кремле прошло секретное совещание, окончательно определявшее сроки «Кубинского похода». Круг лиц был крайне ограничен. От ВМФ присутствовал главком Горшков. Выслушав доклады ответственных о готовности, Хрущев тут же распорядился:
— Операцию начинаем немедленно!
В ночь с 7 на 8 июля от причалов отошли первые груженные войсками и техникой транспорты. «Анадырь» обрел жизнь! А спустя четыре дня в Гавану самолетом прибыла первая рекогносцировочная группа советских офицеров во главе с «товарищем Павловым». Так отныне во всех радиограммах и переговорах должен был именоваться генерал армии Плиев. В состав группы вошли и офицеры ГШ ВМФ, которым предстояло определить места базирования кораблей и начать подготовку к их приему.
Плиев со штабом убыли из Москвы в Гавану тремя транспортными самолетами Ту-114. Старшие офицеры переоделись в гражданскую одежду и были замаскированы под инженеров,
специалистов по сельскому хозяйству или техников по ирригации и осушению, следующих на Кубу в рамках обширной программы гуманитарной помощи.
В середине июля снялся со швартовых и вышел из Мурманска в порт Кабаньяс сухогруз «Мария Ульянова», намереваясь прибыть туда 26 июля. Он был первым судном из общего числа 385 транспортных грузовых судов, которым предстояло покинуть порты, разбросанные по всему Советскому Союзу, и направиться с военными грузами на Кубу. Операция «Анадырь» началась.
Как и предполагали в Генштабе, первые группы транспортов прошли незамеченными. Американцы просто не придали им значения. К началу сентября Военно-морской флот имел уже на Кубе полные запасы боеприпасов: снарядов, авиа- и глубинных бомб. Начали прибывать и ракетные катера, доставляемые сухогрузами.
Первый тревожный сигнал прозвучал 18 сентября, когда в Средиземном море у берегов Туниса американский фрегат запросил один из наших транспортов о характере груза. Ему ответили лаконично: «Сельскохозяйственные машины». Удовлетворившись ответом, американец отвернул в сторону. Вот как описывает свой переход через Атлантику полковник в отставке А. Коваленко, командовавший в то время полком ядерных ракет средней дальности: «Мы вышли из советского порта с приказом следовать к Гибралтару и там вскрыть ящик с соответствующими указаниями. В случае падения в воду или получения помощи судна под иностранным флагом мы должны были говорить, что работаем в «Автоэкспорте» и перевозим автомашины в Гавану.
В то же время был получен приказ воспрепятствовать и отразить любое пиратское нападение или попытку абордажа, для чего у нас имелась батарея 37-миллиметровых пушек и 12 крупнокалиберных пулеметов, спрятанных в ящиках для автомобилей, а также личное оружие. С момента выхода начались соответствующие тренировки для успешного выполнения поставленной задачи. По достижении Гибралтара ознакомились с указаниями, в которых уточнялось, что надо взять курс на Азорские острова и там вскрыть пакет с определенным наименованием.
Когда прибыли в указанный пункт и открыли конверт, смогли прочесть: направляться в порт Мариель (Куба).
После Азорских островов против нас постоянно велась воздушная разведка, и отмечалось частое появление перископов, хотя нельзя было определить, американских или советских подводных лодок. С тем чтобы личный состав полка максимально был похож на членов экипажа, было приказано находиться на верхней палубе по 25—30 человек, которые сменялись через определенные промежутки времени, так как всего в полку было 1200 человек. Весь личный состав следовал во внутренних помещениях и, вследствие высокой температуры, там требовалось использовать шланги для освежения людей водой».