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