Во Втором (латиноамериканском) отделе ПГУ еще раньше, чем в МИДе и Международном отделе ЦК, увидели потенциальные возможности Кастро. Первым разглядел эти задатки молодой сотрудник КГБ Николай Сергеевич Леонов, который владел испанским языком и в пятидесятых годах работал в резидентуре КГБ в Мехико. Выйдя в 1955 году из кубинской тюрьмы, где он провел два года за организацию нападения на военную казарму, Кастро год жил в изгнании в Мексике. Там Кастро обратился в советское посольство с просьбой помочь оружием борющимся с Батистой партизанам. В оружии ему было отказано, но Леонов, пораженный его задатками харизматического лидера партизанской войны, начал с ним встречаться и оказывал ему горячую моральную поддержку. Леонов считал политические идеи Кастро незрелыми и расплывчатыми, но отмечал его решимость сохранить полный личный контроль над созданным им «Движением 26 июля», а также его желание придать своему будущему режиму определенную социалистическую окраску. Он отмечал, что брат Кастро Рауль и его правая рука Че Гевара уже считали себя марксистами. Сначала высказанные Леоновым оптимистические оценки перспектив партизанского движения, которое возникло в декабре 1956 года после возвращения Кастро на Кубу, не нашли отклика в Москве. Но с приходом Кастро к власти прозорливость Леонова и его давние связи с кубинским лидером положили начало его карьере, которая в 1983 году увенчалась его назначением на пост заместителя начальника ПГУ, ответственного за операции КГБ во всей Северной и Южной Америке.
Даже когда Кастро взял власть в январе 1959 года, в Москве продолжали сомневаться в его способности противостоять американскому нажиму. НСП рассматривала союз с ним лишь как тактический ход, такой же, каким была в свое время поддержка режима Батисты. Кастро же застал НСП врасплох, проведя значительную чистку среди старого руководства партии, а потом использовал ее, чтобы быстро установить контроль над всей Кубой. Потом он обратился к Москве за оружием и поддержкой, которые, как он надеялся, помогут ему закрепить завоевания революции и осуществить свою мечту — стать Боливаром Карибского бассейна. В июле 1959 года начальник разведки Кастро майор Рамиро Вальдес отправился в Мехико, где провел секретные переговоры с советским послом и резидентурой КГБ. После этого КГБ направил на Кубу больше сотни своих советников, которые должны были перестроить систему разведки и безопасности Кастро. Среди них было много «лос ниньос» — детей испанских коммунистов, бежавших из Испании и обосновавшихся в России после гражданской войны. Один из старых испанских республиканцев, Энрике Листер Фархан организовал Комитет защиты революции (кубинскую добровольную дружину), который помогал в борьбе с контрреволюционным саботажем. Другой ветеран республиканского движения, генерал Альберто Бахар создал сеть учебных центров по подготовке партизан. Но в Кремле не спешили предоставить открытую поддержку неортодоксальному режиму Кастро. Не в последний раз в качестве «ширмы» были использованы чехи. Осенью в Прагу прибыла кубинская делегация во главе с Раулем Кастро, чтобы обсудить возможности предоставления чехословацкой военной помощи. Несмотря на привычку Рауля спать не раздеваясь и на его страсть к проституткам-блондинкам, его горячая приверженность идеям марксизма произвела на хозяев хорошее впечатление. НСП, по словам заведующего отделом пропаганды Луиса Маса Мартина, пыталась через Рауля повлиять на Фиделя: «Лично я считаю, что Фидель — анархист, но его враждебное отношение к США приведет его в объятия партии, особенно если американцы будут продолжать так глупо реагировать.» Будучи в Праге, Рауль получил от Хрущева приглашение посетить Москву.