Благодаря действиям нелегального резидента ИНО ОГПУ И.Н. Каминского и легального резидента ИНО в США В.Ш. Эльмана этот план был своевременно раскрыт. В итоге переговоры Литвинова с президентом США Ф. Рузвельтом прошли успешно, и 18 ноября 1933 года между СССР и США были установлены дипломатические отношения.
Однако действовать на опережение советской разведке удавалось не всегда. 21 октября 1933 года в консульстве СССР во Львове оуновский боевик Н. Лемек совершил террористический акт против сотрудника внешней разведки А. Майкова, работавшего в Польше в качестве дипломата. На одном из приёмов террорист подошёл к дипломату и в упор расстрелял его из пистолета.
По распоряжению военно-политического руководства СССР в органах госбезопасности началась разработка активных мер по нейтрализации террористических акций ОУН.
Тем временем в органах государственной безопасности произошла очередная глобальная перестановка. 10 июля 1934 года постановлением ЦИК СССР был образован Народный комиссариат внутренних дел СССР, с включением в него аппаратов ОГПУ и НКВД РСФСР. Наркомом назначен Г.Г. Ягода. На базе ОГПУ создаётся Главное управление государственной безопасности (ГУГБ) НКВД СССР. Его куратором стал Я.С. Агранов.
Исполняя распоряжение партии, руководство Иностранного отдела ГУГБ приняло решение о внедрении в среду украинских националистов своего сотрудника. Летом 1934 года выбор был сделан в пользу Павла Судоплатова.
После восьми месяцев обучения Судоплатов был направлен в свою первую зарубежную командировку в сопровождении Лебедя, «главного представителя» ОУН в Украине, а в действительности нашего тайного агента на протяжении многих лет. Лебедь стал для советской разведки ключевой фигурой в борьбе с бандитизмом в Украине в 20-х годах. Его репутация в националистических кругах за рубежом оставалась по-прежнему высокой: Коновалец рассматривал своего представителя как человека, способного провести подготовительную работу для захвата власти ОУН в Киеве в случае войны. От Лебедя, которому нами был разрешен выезд на Запад в 20-х и 30-х годах по нелегальным каналам, нам и стало известно, что Коновалец лелеял планы захвата Украины в будущей войне.
Куратором и одним из основных наставников П.А. Судоплатова в период его подготовки к нелегальной заграничной командировке стал опытный разведчик П.Я. Зубов. Этот человек станет одним из ближайших помощников П.А. Судоплатова во время Великой Отечественной войны.
Первоначальный курс обучения начинающий нелегал закончил в марте 1935 года. В это же время его жена Эмма была переведена в Иностранный отдел НКВД и также прошла специальный курс обучения. В будущей операции её планировалось использовать в качестве связной в Западной Европе между Павлом и Центром. По легенде, связная была студенткой из Женевы. Сам Павел выехал за границу под именем молодого украинского националиста Павла Анатольевича Яценко.
В середине апреля 1935 года Судоплатов выехал в Финляндию в сопровождении Лебедя, который, переправив «племянника» за границу, вернулся через Москву в Харьков.
В период пребывания в Хельсинки Судоплатов находился под опекой «легального» резидента в Финляндии Б.А. Рыбкина («Кин») и его помощницы (впоследствии супруги) З.И. Воскресенской («Ирина»). Эти выдающиеся разведчики внесли также свою лепту в оперативную подготовку молодого разведчика. В это время З.И. Воскресенская в Норвегии координировала работу нелегальной разведывательно-диверсионной группы Э.Ф. Волльвебера («Антон»).
Спустя два месяца от Коновальца в Хельсинки прибыли связные – О. Грибинский из Праги и Д. Андриевский из Брюсселя. Путь в Германию лежал через Швецию, куда Павел и сопровождавшие его лица отправились пароходом.
В июне 1935 года Павел прибыл в Берлин и стал ждать встречи с Е. Коновальцем.
Встреча П. Судоплатова с лидером украинских националистов Е. Коновальцем состоялась летом 1936 года. Встреча проходила на конспиративной квартире, принадлежавшей немецкой разведке. Павел сумел произвести благоприятное впечатление на Коновальца, и в сентябре его направили на три месяца в нацистскую школу в Лейпциге.
В ходе встреч с Коновальцем Судоплатову удалось узнать, что в распоряжении оуновцев уже имеются две бригады, в общей сложности около двух тысяч человек, которые предполагалось использовать в качестве полицейских сил в Галиции (части Западной Украины, входившей тогда в Польшу) и в Германии.
Оуновцы всячески пытались вовлечь Судоплатова в борьбу за власть, которая шла между двумя их главными группировками: «старики» и «молодёжь». Первых представляли Коновалец и его заместитель Мельник, а «молодёжь» возглавляли Бандера и Костарев. Но главной задачей Судоплатова было убедить их в том, что террористическая деятельность в Украине не имеет никаких шансов на успех, так как власти немедленно ликвидируют небольшие очаги сопротивления.
С Коновальцем у Судоплатова складывались неплохие отношения.
«Коновалец привязался ко мне, – вспоминал Судоплатов, – и даже предложил, чтобы я сопровождал его в инспекционной поездке в Париж и Вену с целью проверки положения дел в украинских эмигрантских кругах, поддерживавших его».
Центр решил воспользоваться этой возможностью, чтобы организовать встречу Судоплатову с его курьером. Согласно указанию из Москвы, Павлу надлежало по возможности выйти на такую встречу в Париже и позднее в Вене. Для этого он должен был дважды в неделю появляться между пятью и шестью вечера в определенном месте.
«В первое же своё появление на условленном месте, – рассказывал Павел Анатольевич, – я увидел собственную жену… Усилием воли мне удалось заставить себя удостовериться, что за мной нет никакой слежки, и лишь после этого я приблизился к Эмме. Мне сразу же стало совершенно ясно: место встречи выбрано крайне неудачно, так как сновавшая вокруг толпа не давала возможности проверить, есть ли за тобой наблюдение или нет».
П. Судоплатов информировал Эмму о положении дел в украинских эмигрантских кругах и о той значительной поддержке, которую они получали от Германии. Особенно любопытной показалась ей информация, касающаяся раздоров внутри ОУН.
После приезда Павла в Вену он отправился на место встречи, где и застал своего куратора и наставника по работе в Москве Зубова. Разведчик подробно информировал Зубова о деятельности Коновальца.
Из Вены Судоплатов возвратился в Берлин, где в течение нескольких месяцев шли бесполезные переговоры о возможном развертывании сил подполья в Украине в случае войны. В этот период Павел дважды ездил в Париж, встречался там с лидерами украинского правительства в изгнании. Коновалец предостерегал Павла в отношении этих людей: их не следовало воспринимать серьёзно, поскольку в действительности всё будут решать не эти господа, протиравшие штаны в парижских кафе, а его военная организация.
По окончании командировки П. Судоплатов вернулся в Москву. Вот как он потом вспоминал сам:
«Успешная командировка в Западную Европу изменила моё положение в разведке. О результатах работы было доложено Сталину и Косиору, секретарю ЦК Коммунистической партии Украины, а также Петровскому, председателю Верховного Совета республики. В кабинете Слуцкого, где я докладывал в деталях о своей поездке, меня представили двум товарищам: один из них был Серебрянский, начальник Особой группы при наркоме внутренних дел – самостоятельного и в то время мне неизвестного Центра закордонной разведки органов безопасности, – а другой, по-моему, Васильев, сотрудник секретариата Сталина. Ни того ни другого я прежде не знал».
Скорее всего, Павел Анатольевич имел в виду руководящего работника Коминтерна Б.А. Васильева. Он тесно сотрудничал с Иностранным отделом ГУГВ НКВД и Разведывательным управлением Штаба РККА.
Тем временем П. Судоплатов был назначен вначале оперуполномоченным, а затем помощником начальника 4-го отделения 7-го отдела (внешняя разведка). Весь 1937 год он неоднократно выезжал на Запад в качестве «курьера» оуновского подполья. Как прикрытие использовалась должность радиста на советском грузовом судне «Шилка».
После убийства С.М. Кирова в декабре 1934 года руководство страны принимает решение о применении мер физического воздействия к врагам партии и государства. В числе личных врагов Сталина числились и бывшие служащие советских учреждений за границей, такие как Г.З. Веселовский, оставшийся во Франции, или нелегальный резидент ИНО ОГПУ в Турции Г.С. Агабеков, бежавший в 1930 году из Стамбула в Марсель. В 1931 году он опубликовал в Нью-Йорке книгу под названием «ОГПУ: русский секретный террор». Книга Г.С. Агабекова стала смертным приговором для многих друзей Советского Союза. Только в Персии (Иран) в июле – августе 1932 года было арестовано более четырёхсот человек. В этой связи было принято решение о ликвидации предателя. Вскоре Агабеков был ликвидирован в Париже.
В июле 1937 года во Франции остался нелегал И.Г. Порецкий (Рейс), который направил в Москву письмо с критикой Сталина и проводимой им в Испании политике. Порецкий был крайне опасен в силу его информированности о нелегальных сетях ИНО ОГПУ. Он был ликвидирован сотрудниками ГУГБ во главе с С.М. Шпигельгласом.
Одной из наиболее известных операций внешней разведки является похищение в 1937 году руководителя Российского общевоинского союза Е.К. Миллера, сменившего на этом посту А.П. Кутепова. После того как во второй половине 1930-х годов Миллер через своего представителя в Берлине, генерала Лампе, установил тесные контакты со спецслужбами гитлеровской Германии, в Москве было принято решение о проведении операции по его похищению и вывозу в СССР. Ключевым звеном этой операции являлся бывший командир Корниловской дивизии, помощник Миллера по разведке генерал Н.В. Скоблин, который с 1930 года вместе со своей женой, известной певицей Н.В. Плевицкой, сотрудничал с советской разведкой.
22 сентября 1937 года по приглашению Н.В. Скоблина Миллер направился с ним на виллу под Парижем, где должна была состояться встреча «с представителями германских спецслужб». На самом деле на вилле Миллера поджидала оперативная группа внешней разведки, которая захватила его и через Гавр переправила на теплоходе в СССР. После проведённого в Москве следствия Миллер был предан суду и в 1939 году расстрелян. В операции по захвату Миллера участвовали советские разведчики В. Гражуль, М. Григорьев, Г. Косенко. Руководил операцией С.М. Шпигельглас.