Для переговоров с Ф. Кастро на Кубу вылетела делегация в составе члена Президиума ЦК КПСС Ш. Р. Рашидова, маршала С.С. Бирюзова и генерал-полковника С.П. Иванова. Фидель Кастро принял делегацию незамедлительно. Предложенный план кубинское руководство одобрило, но свое согласие на размещение наших ракет расценило не как помощь Кубе, а как помощь Кубы Советскому Союзу в достижении его собственных целей. С учетом размещения американских ракет в Турции и ядерного превосходства вероятного противника такая логика, несомненно, просматривалась.

По возвращении делегации в Москву состоялось очередное заседание Президиума ЦК КПСС, которое и утвердило операцию «Анадырь». Началась активная подготовка к ее реализации. В конце июня для переговоров с Н.С. Хрущевым и Р.Я. Малиновским в Москву прибыл Рауль Кастро — министр РВС Кубы, доверенное лицо и младший брат Фиделя Кастро. «Несмотря на свою молодость, этот красивый смуглый человек, — вспоминал генерал армии А.И. Грибков, — отличался зрелостью суждений в… военных вопросах. Все говорило о том, что школа революционной борьбы и партизанских боев для него не прошла зря. С ним было легко работать».

Переговоры с Раулем Кастро, как и вся подготовка к операции «Анадырь», проходили в строжайшей тайне. Интересна такая деталь. В процессе переговоров с Р. Кастро впервые разрешили привлечь к работе машинистку и то только потому, что документы пришлось печатать на машинке с латинским шрифтом.

При составлении проекта договора генштабисты вооружились справочниками и массой документов по международно-правовым нормам — консультироваться с юристами-международниками было нельзя. Наконец проект договора о военном сотрудничестве Кубы и СССР был готов. Его суть заключалась в том, что советскому военному контингенту совместно с кубинскими войсками надлежало защитить территорию Кубы от внешней агрессии. При этом войска каждой из сторон оставались в подчинении своих правительств. Советские военнослужащие были обязаны выполнять кубинские законы. Территория для размещения боевой техники и советских войск предоставлялась во временное пользование. Договор предполагалось заключить сроком на 5 лет с возможностью его последующей пролонгации. Проект договора под названием «Договор между Правительством Республики Куба и Правительством Союза Советских Социалистических Республик о размещении Советских Вооруженных Сил на территории Республики Куба» подписали Р.Я. Малиновский и Р. Кастро.

Рассмотрев в начале августа проект договора у себя на родине, кубинская сторона внесла ряд поправок. Дополненный и уточненный по отдельным статьям проект договора с личным письмом Ф. Кастро на имя Н.С. Хрущева в Москву привез Э. Че Гевара. Кубинская сторона полагала, что некоторые изменения текста, не затронувшие суть договора, будут способствовать усилению его политического воздействия.

В преамбуле договора говорилось: «Правительство Республики Куба и Правительство Союза Советских Социалистических Республик согласились подписать настоящий Договор, исполненные решимости предпринять необходимые шаги для совместной защиты законных прав Кубы и Советского Союза, имея, кроме того, в виду настоятельную необходимость принятия мер для обеспечения взаимной безопасности перед лицом возможной агрессии против Республики Куба и СССР, желая договориться по всем вопросам, касающимся поддержки, которую Советские Вооруженные Силы окажут в деле защиты национальной территории Кубы в случае агрессии». Таким образом, по инициативе кубинской стороны речь в договоре шла не только о безопасности Кубы, но и о безопасности Советского Союза от американской агрессии.

27 августа в Москве было получено письмо за подписями Фиделя Кастро и Президента Республики Куба Освальдо Дортикоса. В письме говорилось, что, «питая особое доверие к личности, такту и умению Эрнесто Че Гевары, правительство Республики Куба облекло его полнотой власти и уполномочило для подписания договора военного характера». Как вспоминал генерал А.И. Грибков, «Че Гевара поразил нас всех своим несгибаемым духом, поистине революционной одержимостью. Это был человек высокой культуры, не только пламенный революционер, но и известный поэт, выражавший в своих стихах революционный настрой, верность делу кубинской революции и ее вождю». Подготовленный и согласованный договор, и протокол к нему Э. Че Гевара подписывать не стал. Маршал Р.Я. Малиновский и он его лишь парафировали. Между тем подготовка операции «Анадырь» шла полным ходом.

7 июля 1962 года Н.С. Хрущев лично утвердил руководящий состав Группы войск. Генерал-лейтенант П.Б. Данкевич стал первым заместителем командующего и командующим ракетными войсками. За ним следовали генерал-майор П.М. Петренко — член военного совета, начальник политуправления; генерал-лейтенант П.В. Акиндинов — начальник штаба; генерал-лейтенант авиации С.Н. Гречко — заместитель главнокомандующего по противовоздушной обороне; вице-адмирал Г.С. Абашвили — заместитель главнокомандующего по ВМФ и другие генералы.

Штаб Группы приступил к разработке графика отправки войск. Первой на Кубу планировалось направить ракетную дивизию. На приведение ее в боевую готовность требовалось самое большое время. Однако вскоре пришли к заключению, что это нецелесообразно. В портах выгрузки и на боевых позициях ракетчики оказались бы беззащитными перед авиацией и диверсионными группами возможного противника. По этой причине решили сначала перебросить на остров зенитно-ракетные и мотострелковые части и только потом полки, оснащенные ракетами «Р-12» и «Р-14». Об этом Р.Я. Малиновский доложил Н.С. Хрущеву и получил одобрение.

В соответствии с планом операции 10 июля 1962 года первой на Кубу отправилась рекогносцировочная группа. Через несколько дней вылетела вторая группа, под видом специалистов сельского хозяйства, инженеров и техников по мелиорации. Но военная выправка, несомненно, выдавала «специалистов». Обе группы направлялись на Кубу как бы для продолжения работ, начатых визитом Ш. Р. Рашидова. Кстати, прибывшие на Кубу первые «специалисты по сельскому хозяйствуй сделали поразительный по своей военной безграмотности вывод о том, что на Кубе можно легко и скрытно разместить ракеты, так как там (!) много пальмовых рощ.

Между тем подготовка выделенных к отправке войск подходила к концу. В один из июльских дней Н.С. Хрущеву было доложено о готовности Министерства обороны к реализации плана «Анадырь»: «Все войска, предусмотренные по перечню боевого состава, отобраны, укомплектованы и готовы к отправке. Произведено планирование всех мероприятий по доставке советских войск на остров Куба в течение четырех месяцев: июль-октябрь. Первым днем погрузки назначено 12 июля 1962 года».