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