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