Для работы по украинским националистам, на которую нацеливал чекистов В. Р. Менжинский, необходимы были кадры. А. А. Слуцкий, занявший к тому времени пост начальника Иностранного отдела, предложил Судоплатову стать разведчиком-нелегалом и работать за рубежом по украинской линии.
«Сначала это показалось мне нереальным, — вспоминал Судоплатов, — поскольку опыта работы за границей у меня не было и я ничего не знал об условиях жизни на Западе. К тому же мои знания немецкого, который должен был мне понадобиться в Германии и Польше, где предстояло работать, равнялись нулю.
Однако чем больше я думал об этом предложении, тем более заманчивым оно мне представлялось. И я согласился. После чего сразу приступил к интенсивному изучению немецкого языка — занятия проходили на явочной квартире пять раз в неделю. Опытные инструкторы обучали меня также приемам рукопашного боя и владению оружием. Исключительно полезными для меня были встречи с заместителем начальника Иностранного отдела ОГПУ — НКВД Шпигельглазом. У него был большой опыт работы за границей в качестве нелегала — в Китае и Западной Европе. В начале 1930-х годов в Париже “крышей” ему служил рыбный магазин, специализировавшийся на продаже омаров, расположенный возле Монмартра.
После восьми месяцев обучения я был готов отправиться в свою первую зарубежную командировку в сопровождении Лебедя, “главного представителя” ОУН на Украине, а в действительности нашего тайного агента на протяжении многих лет».
К этому времени жена Судоплатова Эмма Карловна также была переведена в Иностранный отдел и прошла специальный курс подготовки. Ей предстояло под видом студентки из Женевы поддерживать связь мужа с Центром, периодически встречаясь с ним в европейских странах.
Так началась новая жизнь Павла Судоплатова — советского разведчика-нелегала. Перед ним была поставлена конкретная задача: под видом «племянника» Лебедя Павла Яценко сблизиться с представителями ОУН в европейских странах, пройти у них необходимую проверку и в конечном итоге попытаться войти в окружение Коновальца.
Следует отметить, что внедренный в ОУН агент ОГПУ Лебедь был старым другом Коновальца. В годы Первой мировой войны он вместе с ним воевал в качестве офицера австро-венгерской армии против России на Юго-Западном фронте. В 1915–1918 годах находился в лагере для военнопленных под Царицыном. В Гражданскую войну стал заместителем Коновальца и командовал пехотной дивизией, сражавшейся против частей Красной армии на Украине. После бегства Коновальца в Польшу Лебедь был направлен им на Украину для организации подпольной сети ОУН. Там он был арестован, а затем завербован органами ОГПУ. Выбор перед ним был простой: или работать на ОГПУ, или умереть. Однако необходимо подчеркнуть, что он сотрудничал с советскими органами государственной безопасности исключительно добросовестно, неоднократно выезжал с конкретными заданиями ОГПУ за границу и, видимо, никогда не помышлял о побеге.