Понятно, что данное соглашение было достигнуто в обход руководства Кубы, и Н. С. Хрущев, конечно, понимал, что Фидель Кастро и его ближайшие соратники воспримут все эти договоренности с Вашингтоном как предательство со стороны Москвы. Поэтому для ведения переговоров с ними был отряжен самый опытный член Президиума ЦК Анастас Иванович Микоян, который был неплохо знаком со всеми членами высшего кубинского руководства. Правда, перед своим прибытием в Гавану 3 ноября он провел переговоры с Дж. Макклоем и Э. Стивенсоном, которые дали ему гарантии ненападения на Кубу, и только на следующий день он вылетел в кубинскую столицу, где ему предстояли крайне тяжелые, даже с психологической точки зрения переговоры с Ф. Кастро, Р. Кастро и Э. Че Геварой. Но сам А. И. Микоян прекрасно сознавал всю важность своей миссии, о чем зримо говорит тот хорошо известный факт, что он не вернулся в Москву на похороны собственной супруги Ашхен Лазаревны Туманян, скончавшейся от давнего заболевания сердца 5 ноября 1962 года. В ходе жарких и продолжительных дискуссий, шедших два дня, все же была достигнута очень важная договоренность, что кубинская сторона более не будет настаивать на сохранении советских баллистических и тактических ракет, ядерных зарядов и фронтовых бомбардировщиков, а советская сторона подпишет с Гаваной новый договор о военно-техническом сотрудничестве, в котором будет оговорено сохранение на территории Кубы всего неядерного оружия, всей военной техники и советских военных специалистов, способных обучить кубинцев владению этим оружием и техникой.

Тогда же, в начале ноября, для ведения конкретных переговоров с янками в Нью-Йорк был направлен зам. министра иностранных дел СССР Василий Васильевич Кузнецов, которому пришлось вести долгие и трудные баталии с постпредом США в ООН Э. Стивенсоном и главой ЦРУ Дж. Маккоуном. Юридической базой для этих переговоров стал совместный советско-кубинский проект Протокола, состоявший из 15 пунктов, который 15 ноября 1962 года был направлен и.о. генсека ООН У Тану, занявшему этот пост после трагической гибели Д. Хаммаршельда в Родезии. Однако американская сторона делала все возможное для затягивания переговоров и резко выступала против их ведения в рамках СБ ООН. Но тем не менее 7 января 1963 года В. В. Кузнецов и Э. Стивенсон обратились с совместным письмом к только что избранному новым Генсеком ООН бирманцу У Тану, где отметили, что, хотя обоим правительствам «не удалось разрешить все проблемы», связанные с кризисом, они все же считают, что достигнутая степень согласия между ними по урегулированию этого кризиса «делает ненужным сохранение данного вопроса в повестке дня Совета Безопасности ООН». Кстати, как совершенно справедливо заметил Д. Е. Косырев, эти переговоры «чародея» дипломатии В. В. Кузнецова «стали бы забытой страницей истории, если бы не воспоминания «Во власти дипломатии» его тогдашнего помощника» Бориса Иосифовича Поклада, который сопровождал его в этой поездке[635].