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