В мае 1959 года Шелепин организовал в Москве крупнейшую со времени создания ЧК конференцию по вопросам разведывательной деятельности, на которой были обсуждены приоритетные задачи КГБ. В конференции приняли участие две тысячи сотрудников КГБ, представитель от Политбюро Алексей Илларионович Кириченко, члены Центрального Комитета партии и представители министерств обороны и внутренних дел. Шелепин выступил с комплексной программой мобилизации усилий разведслужб всех стран советского блока на достижение долгосрочных целей советской политики и устранение угрозы со стороны США, их союзников по НАТО и Японии. Управлению Д предписывалось согласовывать свою программу "активных действий" с Международным отделом ЦК и госаппаратом.
Несмотря на свою довольно изощренную программу "активных действий", Шелепин не собирался отказываться от более радикальных "специальных операций" за рубежом. При Серове Тринадцатый отдел ПГУ, занимавшийся "мокрыми делами", был замешан в нескольких публичных скандалах. После неудачи во Франкфурте, когда не удалось ликвидировать Георгия Околовича, руководителя эмигрантской организации "Народно-трудовой союз" (НТО, а непосредственный исполнитель акции сотрудник КГБ Николай Хохлов бежал на Запад в 1954 году, Тринадцатый отдел нанял в 1955 году профессионального убийцу - немца Вольфганга Вильдпретта для ликвидации президента НТС Владимира Поремского. Но, как и Хохлов, Вильдпретт в последний момент передумал и сообщил обо всем западногерманской полиции. Неудачей закончилась и попытка Тринадцатого отдела отравить Хохлова радиоактивным таллием в сентябре 1957 года (этот метод был выбран в надежде, что следы таллия не будут обнаружены при вскрытии). Вслед за неудачами последовали успешные операции по ликвидации двух лидеров украинской эмиграции в Западной Германии - главного идеолога НТС Льва Ребета в октябре 1957 года и руководителя Организации украинских националистов (ОУН) Степана Бандеры в октябре 1959 года. Эти операции убедили Шелепина и Хрущева, с санкции которого они и проводились, что убийства отдельных лиц по-прежнему являются необходимым элементом деятельности КГБ за рубежом.
Исполнителем обеих акций Тринадцатого управления был Богдан Сташинский, которому было всего 25 лет, когда он убил Ребета. Сташинский готовил операции в городке КГБ в Карлсхорсте. Орудие убийства было разработано в оружейной лаборатории КГБ ("хозяйство Железного") и представляло собой газовый пистолет, который стрелял струей ядовитого газа из разбиваемой ампулы с цианистым калием. При попадании газ вызывал остановку сердца. Тринадцатый отдел правильно рассчитал, что ничего не подозревающий патологоанатом, скорее всего, напишет в заключение, что причиной смерти явилась сердечная недостаточность. Сташинский сначала испытал действие пистолета на собаке: он отвел ее в лес неподалеку от Карлсхорста, привязал к дереву и выстрелил. Собака забилась в конвульсиях и через несколько секунд умерла. Убедившись таким образом в безотказности своего оружия, Сташинский убил и Ребета, и Бандеру, подкараулив их в темном подъезде. В декабре 1959 года Сташинского вызвали в Московский центр, где Шелепин в торжественной обстановке вручил ему орден Красного Знамени и зачитал приказ о награждении, в котором говорилось, что награда вручается "за успешное выполнение особо важного задания правительства". Сташинскому сообщили, что он направляется на курсы, где продолжит изучение немецкого языка и выучит английский, после чего он три или пять лет проведет на Западе, выполняя новые "задания" того же характера. "Работа вас ждет нелегкая, но почетная," - сказал ему тогда Шелепин.
Однако, как Хохлов и Вильдпретт, Сташинский позднее по-иному взглянул на убийства. Немало этому способствовала Инга Поль - его антикоммунистически настроенная подруга из Восточной Германии, на которой он женился в 1960 году. В августе 1961 года, за день до того, как пути бегства с Востока перекрыла Берлинская стена, супруги перебежали на Запад. Сташинский признался в убийстве Ребета и Бандеры, его судили в Карлсруэ в октябре 1962 года и приговорили к восьми годам тюремного заключения за соучастие в убийстве. Судья заявил, что главным виновником является Советское правительство, которое узаконило политические убийства. В КГБ тут же полетели головы. По словам Анатолия Голицына, бежавшего на Запад через четыре месяца после Сташинского, как минимум семнадцать сотрудников КГБ были уволены или разжалованы. Но что самое важное, измена Хохлова и Сташинского заставила Политбюро и руководство КГБ по-новому взглянуть на "мокрые дела" и связанный с ними риск. После широкой международной огласки, которую получил суд над Сташинским, Политбюро решило отказаться от организованных КГБ убийств как обычного средства проведения политики за пределами стран советского блока и прибегало к этому средству лишь в редких случаях, как это было, например, в Афганистане в декабре 1979 год, когда был убит президент Хафизулла Амин.
В конце холодной войны, как, впрочем, и в ее начале, внешняя деятельность КГБ была направлена прежде всего против "главного противника". В начале шестидесятых КГБ впервые предоставилась возможность создать крупную оперативную базу в Латинской Америке, "под боком" у США. Это стало возможным после того, как к власти на Кубе в результате свержения режима Батисты в январе 1959 года пришел Фидель Кастро. До этого момента Кремль с глубоким пессимизмом относился к перспективам революции в Латинской Америке, полагая, что успешный коммунистический переворот там невозможен, так как слишком велико влияние США. Сам Кастро, получивший привилегированное воспитание, даже по меркам богатых кубинских землевладельцев, свое политическое вдохновение первоначально черпал в Партии кубинского народа ("ортодоксы") и в идеалах ее основателя - антимарксиста Эдуарде Чибаса. До лета 1958 года Кубинская компартия - НСП продолжала утверждать, при поддержке Москвы, что режим Батисты можно свергнуть лишь путем народного восстания кубинских рабочих под руководством коммунистов.
Во Втором (латиноамериканском) отделе ПГУ еще раньше, чем в МИДе и Международном отделе ЦК, увидели потенциальные возможности Кастро. Первым разглядел эти задатки молодой сотрудник КГБ Николай Сергеевич Леонов, который владел испанским языком и в пятидесятых годах работал в резидентуре КГБ в Мехико. Выйдя в 1955 году из кубинской тюрьмы, где он провел два года за организацию нападения на военную казарму, Кастро год жил в изгнании в Мексике. Там Кастро обратился в советское посольство с просьбой помочь оружием борющимся с Батистой партизанам. В оружии ему было отказано, но Леонов, пораженный его задатками харизматического лидера партизанской войны, начал с ним встречаться и оказывал ему горячую моральную поддержку. Леонов считал политические идеи Кастро незрелыми и расплывчатыми, но отмечал его решимость сохранить полный личный контроль над созданным им "Движением 26 июля", а также его желание придать своему будущему режиму определенную социалистическую окраску. Он отмечал, что брат Кастро Рауль и его правая рука Че Гевара уже считали себя марксистами. Сначала высказанные Леоновым оптимистические оценки перспектив партизанского движения, которое возникло в декабре 1956 года после возвращения Кастро на Кубу, не нашли отклика в Москве. Но с приходом Кастро к власти прозорливость Леонова и его давние связи с кубинским лидером положили начало его карьере, которая в 1983 году увенчалась его назначением на пост заместителя начальника ПГУ, ответственного за операции КГБ во всей Северной и Южной Америке.
Даже когда Кастро взял власть в январе 1959 года, в Москве продолжали сомневаться в его способности противостоять американскому нажиму. НСП рассматривала союз с ним лишь как тактический ход, такой же, каким была в свое время поддержка режима Батисты. Кастро же застал НСП врасплох, проведя значительную чистку среди старого руководства партии, а потом использовал ее, чтобы быстро установить контроль над всей Кубой. Потом он обратился к Москве за оружием и поддержкой, которые, как он надеялся, помогут ему закрепить завоевания революции и осуществить свою мечту - стать Боливаром Карибского бассейна. В июле 1959 года начальник разведки Кастро майор Рамиро Вальдес отправился в Мехико, где провел секретные переговоры с советским послом и резидентурой КГБ. После этого КГБ направил на Кубу больше сотни своих советников, которые должны были перестроить систему разведки и безопасности Кастро. Среди них было много "лос ниньос" - детей испанских коммунистов, бежавших из Испании и обосновавшихся в России после гражданской войны. Один из старых испанских республиканцев, Энрике Листер Фархан организовал Комитет защиты революции (кубинскую добровольную дружину), который помогал в борьбе с контрреволюционным саботажем. Другой ветеран республиканского движения, генерал Альберто Бахар создал сеть учебных центров по подготовке партизан. Но в Кремле не спешили предоставить открытую поддержку неортодоксальному режиму Кастро. Не в последний раз в качестве "ширмы" были использованы чехи. Осенью в Прагу прибыла кубинская делегация во главе с Раулем Кастро, чтобы обсудить возможности предоставления чехословацкой военной помощи. Несмотря на привычку Рауля спать не раздеваясь и на его страсть к проституткам-блондинкам, его горячая приверженность идеям марксизма произвела на хозяев хорошее впечатление. НСП, по словам заведующего отделом пропаганды Луиса Маса Мартина, пыталась через Рауля повлиять на Фиделя: "Лично я считаю, что Фидель - анархист, но его враждебное отношение к США приведет его в объятия партии, особенно если американцы будут продолжать так глупо реагировать." Будучи в Праге, Рауль получил от Хрущева приглашение посетить Москву.
В октябре 1959 года, пока Рауль был в Праге, в Гавану прибыла советская "культурная делегация" во главе с бывшим резидентом КГБ в Буэнос-Айресе Александром Ивановичем Шитовым (он же Алексеев), чтобы подготовить почву для установления дипломатических отношений. Шитов презентовал Фиделю бутылку водки, несколько банок икры и фотоальбом с видами Москвы. Потом он поведал ему о том, с каким "огромным восхищением" советский народ относится к нему лично и к кубинской революции. Кастро открыл бутылку и послал за крекерами для икры. "Какая водка! Какая икра замечательная!" - воскликнул он одобрительно. "Пожалуй, стоит наладить с Советским Союзом торговые связи." "Это прекрасно, Фидель, - ответил Шитов. - А как насчет самого главного - дипломатических отношений?" Когда наконец в мае 1960 года Советский Союз полностью признал режим Кастро, установив с ним дипломатические отношения, Шитов остался в Гаване формально на должности советника по культуре и представителя ТАСС, а на самом деле - в качестве резидента КГБ. Преодолев свои первоначальные колебания, Хрущев теперь публично выступал с горячей поддержкой кубинского режима (но пока не лично Кастро). 9 июля в своем воинствующе антиамериканском выступлении он заявил: "Мы все сделаем, чтобы поддержать Кубу в ее борьбе… Теперь США не так уж недосягаемы, как когда-то." На следующий день Че Гевара похвалился, что Кубу защищает "величайшая военная держава в истории". Кастро и его соратники стали в своих речах заявлять, что кубинская революция - "лишь первый шаг на пути к освобождению Латинской Америки". Несмотря на то, что идеологический фундамент Кастро все еще вызывал сомнения, его успех в удержании и укреплении власти заставил КГБ и Кремль изменить свою стратегию в Латинской Америке. На смену традиционной ориентации на идейно правильные коммунистические партии пришла политика "браков по расчету" с национально-освободительными движениями, которые пользовались более широкой поддержкой масс. После провала высадки десанта в заливе Кочинос, осуществленной при поддержке ЦРУ в апреле 1961 года с целью свержения Кастро, Москва еще больше изменила свое мнение о возможностях США. Оказалось, что США были уязвимы даже на своем собственном "заднем дворе".
Несмотря на то, что Кастро относился с растущей неприязнью к советскому послу Сергею Кудрявцеву, у него сложились теплые дружеские отношения с резидентом КГБ Александром Шитовым. В марте 1962 года Кастро выступил по телевидению, объявив о роспуске старой компартии Кубы, на которую ориентировался Кудрявцев, а потом распрощался с Кудрявцевым, попросив, чтобы новым послом СССР назначили Шитова, который все еще работал под псевдонимом Алексеев. Просьбу Кастро удовлетворили. Шесть месяцев спустя укрепившиеся советские позиции на Кубе привели к крупнейшему со времен Второй мировой войны международному кризису. В начале 1962 года, разместив в Великобритании и Турции свои новые межконтинентальные ракеты "Минитмен" в дополнение к уже имевшимся там ракетам средней дальности, США удалось добиться явного преимущества в гонке вооружений. Хрущев же посчитал, что может быстро добиться ядерного превосходства над американцами, разместив советские ракеты на Кубе - в каких-то 90 милях от США. Идя на эту авантюру, Хрущев не столько основывался на анализе разведывательной информации, сколько на своей собственной, явно заниженной оценке решительности США вообще и молодого президента Джона Ф. Кеннеди в частности. Как сказал Хрущев, беседуя с американским поэтом Робертом Фростом, западные демократии "слишком либеральны, чтобы драться". Нерешительность Кеннеди во время неудачной операции в заливе Кочинос убедила Хрущева в том, что у молодого президента "кишка тонка". "Я наверняка знаю, что Кеннеди мягкотел, и вообще у него не хватает решительности, чтобы принять серьезный вызов." Тайно разместив на Кубе ядерные ракеты, Советский Союз мог бы потом поставить Кеннеди перед фактом, с которым тот будет вынужден смириться. Летом 1962 года советские инженеры приступили к строительству стартовых позиций для ядерных ракет с радиусом действия свыше трех тысяч километров, которые могли долететь до основных городов на восточном побережье США всего за несколько минут.
Во всех предшествующих кризисах холодной войны советская разведка была поставлена значительно лучше, чем западная. Во время же Карибского кризиса в октябре 1962 года США впервые были столь же хорошо информированы, как и Кремль, а может, даже и лучше. Отчасти это объяснялось тем, что эпицентр кризиса находился всего лишь в девяноста милях от границ США. Разведывательное превосходство СССР было также подорвано двумя крупными достижениями Запада в технике сбора информации. Одно из этих достижений было сделано в области воздушной разведки. В 1955 году президент Эйзенхауэр предложил Советскому Союзу политику "открытого неба", которая позволила бы обеим сторонам вести воздушное наблюдение за перемещениями войск. Когда Россия отказалась от этого предложения, США в одностороннем порядке стали совершать облеты советской территории на самолетах "У-2", способных подниматься на высоту до 21.000 метров. Перехват самолета "У-2" в 1960 году и состоявшийся в Москве открытый процесс над пилотом Гэри Пауэрсом лишь ненадолго отбросил США назад. Уже через несколько месяцев после этого в США был запущен первый спутник-шпион, хотя разрешающая способность спутниковых фотографий была ниже, чем у фотографий, сделанных с "У-2". К 1963 году Кремль молчаливо смирился со спутниковой разведкой, и обе стороны начали широко использовать разведывательные спутники, в том числе для ведения ЭР и фотографирования различных объектов.
В середине пятидесятых годов Запад также значительно усовершенствовал работу агентурной разведки в Советском Союзе, хотя успехи в этой области были не такие впечатляющие, как в разведке воздушно-космической. Весной 1961 года СИС завербовала самого крупного западного агента времен холодной войны - полковника Олега Владимировича Пеньковского, офицера ГРУ, работавшего в Государственном комитете по науке и технике.
Среди друзей Пеньковского был начальник ГРУ генерал Иван Александрович Серов и начальник Главного управления ракетных войск и артиллерии (ГРАУ) Главный маршал артиллерии Сергей Сергеевич Варенцов. Сведения, добытые Пеньковским (почти 5.500 кадров, отснятых за полтора года микрофотокамерой "Минокс"), представляли огромную ценность. Среди них были последние данные о советских межконтинентальных баллистических ракетах (их оказалось на несколько тысяч меньше, чем предполагали США), степенях боевой готовности, очередности проверок и пуска советских стратегических ракет, статистические данные о точности попадания ракет и выявленных в ходе огневых испытаний дефектах. Сведения Пеньковского о том, что в СССР возросла роль ракет и программ космических вооружений, заставили НАТО всерьез пересмотреть свою стратегию. В самые напряженные моменты над обработкой данных Пеньковского, который работал одновременно на СИС и ЦРУ, трудились двадцать американских и десять английских аналитиков. Эффективный сбор разведданных был необходим Западу для того, чтобы мирным путем урегулировать Карибский кризис еще до того, как на Кубе будут размещены ракеты. 14 октября 1962 года самолет "У-2", совершивший облет кубинской территории, сделал первые снимки строящихся стартовых позиций для баллистических ракет. Аналитикам ЦРУ удалось определить характер сооружений благодаря секретным документам, в которых содержались подробные сведения об этапах строительства стартовых позиций. Эти документы Пеньковский тайно переснял в Главном ракетно-артиллерийском управлении, куда ему удалось проникнуть благодаря дружбе с Главным маршалом артиллерии Варенцовым. 16 октября фотографии легли на стол президента США. Кеннеди отреагировал на это известие, создав засекреченный комитет по управлению кризисом, известный как Иском (Исполнительный комитет Совета национальной безопасности), который в течение последующих тринадцати дней поминутно следил за развитием событий. К 19 октября облеты "У-2" предоставили Искому доказательства существования девяти строящихся пусковых площадок для баллистических ракет. 22 октября Кеннеди объявил об установлении американской блокады для обеспечения "строгого карантина на поставки всех видов наступательных вооружений на Кубу". Почти на целую неделю над миром нависла угроза ядерной катастрофы.