В принципе планировалось послать к берегам Кубы две эскадры кораблей – надводную и подводную, но впоследствии от этого отказались.
Решение о готовности начать такую операцию было принято 24 мая 1962 г. на заседании президиума ЦК КПСС и Совета Обороны по докладу министра обороны Родиона Малиновского. Чтобы согласовать операцию и получить «добро» со стороны кубинцев, в Гавану была направлена специальная делегация во главе с Ш. Рашидовым, которая вернулась 10 июня с согласием кубинцев.
До настоящего времени ведутся дискуссии, разумно ли было предпринимать столь масштабную военную операцию, не подкрепив ее международно-правовой базой в виде, скажем, предварительного заключения военного договора между СССР и Кубой. Приходилось слышать впоследствии, что А. И. Микоян и А. А. Громыко робко пытались обратить внимание Хрущева на эту сторону дела, но верх взяло мнение военных о том, что, в случае предварительного обнародования планов проведения операции «Анадырь», американцы не позволили бы осуществить ее и сорвали бы ее на самом раннем этапе, когда они обладали всеми преимуществами стратегического характера, а у Советского Союза не было адекватных условий для контрходов. В итоге ставка была сделана на проведение операции в условиях секретности, а мир должен был узнать о свершившемся факте 25–27 ноября 1962 г., когда планировалось прибытие на Кубу официальной делегации Советского Союза во главе с Никитой Хрущевым для подписания соответствующего договора с Фиделем Кастро.
Среди военных оказался один смелый генерал, А. А. Дементьев, который в то время работал главным советником у Фиделя Кастро. Он возразил Н. Хрущеву, заметив, что сохранить в секрете всю операцию «Анадырь» до конца не удастся из-за открытости будущих ракетных позиций для разведывательных самолетов США. Сидевший на совещании рядом с ним Родион Малиновский, по свидетельству очевидцев, толкал под столом А. Дементьева, пытаясь «вразумить» его, но тот стоял непреклонно и, как оказалось впоследствии, был прав.
Операция «Анадырь» с точки зрения штабной проработки и организации осуществления, безусловно, была весьма успешной. Были приняты меры по зашифровке и легендированию всех погрузочных работ. Например, на борт судов, капитаны которых не знали портов назначения, грузились лыжи, теплая одежда, которые якобы предназначались для войсковых учений в полярных и приполярных районах. Каждому капитану вручались три пакета. Первый они должны были вскрыть при выходе из территориальных вод СССР. В нем содержалось предписание следовать к Босфору. Затем после выхода из Мраморного моря надо было руководствоваться содержимым второго пакета, а в нем говорилось, что надлежит держать курс на Гибралтар. Только после выхода в Атлантику следовало открыть третий пакет, где лежал приказ брать курс на Кубу.