Когда некоторые руководители в Советском Союзе почувствовали возможность расширения советского влияния в Латинской Америке, Алексеев был отозван из Аргентины и в 1958 году переведен на работу в Комитет по культурным связям с зарубежными связями при Совете Министров СССР, где он мог применить свои знания и опыт, полученные в Латинской Америке. Именно КГБ в качестве сотрудника этого Комитета направил его в Гавану со специальной миссией: установить контакт с высшими руководителями Кубы. Алексеев был среди тех, кто признал необычность кубинской революции. Она не походила на типичный латиноамериканский переворот. Ни военные, ни представитель США на месте не взяли под свой контроль новое правительство. В январе 1959 года Алексеев попросил направить его на Кубу в качестве наблюдателя. Руководство КГБ согласилось, но кубинцы выдали ему визу лишь через семь месяцев.
Наконец, 1 октября 1959 года Алексеев прибыл на Кубу. В аэропорту его встречал Карлос Рафаэль Родригес, редактор коммунистической газеты «Ла нотсиас де ой». Родригес был важной фигурой в революции. Символ сотрудничества между Движением 26 июля и коммунистами, летом 1958 года он ушел в горы и стал советником Фиделя Кастро
Алексеев, однако, был осторожен с Карлосом Рафаэлем Родригесом и руководством НСП Он чувствовал, что Родригес преувеличивает свое значение в кубинской революции. Карлос Рафаэль Родригес не уставал превозносить свою роль в разработке концепции радикальных экономических реформ. Карлос Рафаэль Родригес не считал Кастро коммунистом Брат Фиделя Рауль и Че были «полностью на стороне левых». Что же касается Фиделя, то он, по мнению Карлоса Рафаэля Родригеса, был сам по себе, хотя душой был с коммунистами. Так думал и Алексеев Но правда ли, что с весны у Рауля якобы появились мысли о насильственном устранении брата{11}. Никаких доказательств, только натянутые отношения Когда Карлос Рафаэль Родригес предложил Алексееву представить его коммунистическим лидерам, Алексеев уклонился от этого Он работал со многими некоммунистами, а просоветски настроенными людьми и знал, что они могут быть полезны СССР. Еще находясь в Москве, Алексеев был удивлен антиамериканским характером кубинской революции. Именно это более всего импонировало Москве. В первый период советско-кубинских отношений коммунистический аспект кастровской революции стоял на втором плане{12}.
Алексеев много гулял по Гаване Он был уверен, что никто не знает о его пребывании на острове, и надеялся надолго сохранить это в тайне. Подобно герою американского актера Вуди Аллену Зелига, он одновременно появлялся в разных местах.
У Кастро была привычка произносить массу публичных речей. Алексеев практически не пропускал ни одного из выступлений Фиделя. Сидя в кафе, он просматривал все газеты, которые мог достать. Все они были резко антисоветскими, причем антисоветизм сочетался с ненавистью к американскому империализму. «Я не мог понять, — вспоминал он позже, — что это за революция, куда она идет». Алексеев мог прояснить ситуацию, только встретившись с Фиделем Кастро, а не с Карлосом Рафаэлем Родригесом или Блас Рока из НСП. И хотя Рауль Кастро уже работал с советскими эмиссарами, Алексеев не чувствовал необходимости встречи с ним. Заручившись поддержкой революционеров, он решил выйти на Фиделя Кастро через Че Гевара — истинного революционера, которого Москва считала таким же популярным на Кубе, как и Фиделя. С помощью кубинского радиожурналиста, который в составе делегации посетил Москву летом 1958 года, Алексеев вышел на Че. Их встреча состоялась 12 октября ночью.
Че объяснил Алексееву, что социализм — единственный путь обретения суверенитета. «Нет другого пути к независимости, кроме построения социалистического общества и дружбы с лагерем социализма». Однако, подчеркнул Че, Куба может защитить себя. Он признал, что это его личное мнение. В революционном руководстве некоторые друзья СССР, например Рауль, придерживаются иного мнения.
Встреча началась неудачно. Для подарка астматику Че, заядлому курильщику, Алексеев купил блок сигарет, при этом он не обратил внимания на торговую марку — Техас. «Он взглянул на сигареты… задрожал и посмотрел мне в глаза. „Вы знаете, что такое Техас? Это — бывшая республика Америки, которую захватили североамериканцы“. После минутной неловкости встреча пошла гладко. Одним словом, — говорил позже Алексеев, — это был разговор единомышленников». Теперь он знал, «что есть что». То же почувствовал и Че. Беседа продолжалась до пяти часов утра. Че Гевара организовал встречу Алексеева с Фиделем Кастро. 16 октября в два часа ночи в номере Алексеева раздался звонок в дверь. Мужской голос спросил: «Сеньор Алексеев? Вы просили о встрече с комманданте Фиделем Кастро? Он примет Вас. Готовы ли Вы поехать к нему немедленно?» Алексеев вспоминает: «Я надел темный костюм, серый галстук; одним словом, как на прием к премьер-министру».