Впервые за границу В. Лебедь-Хомяк (1899 г.р.) попал в начале 1933 года. Якобы спасаясь от арестов, он по хорошо сфабрикованным документам устроился на корабль. В Бельгии остался и восстановил связь с Коновальцем.

Именно от В. Лебедя была получена информация о командировке в США пятерых боевиков во главе с Мишугой для теракта против наркома иностранных дел СССР М. Литвинова в 1933 году. Террористы были арестованы.

В 1935 году Судоплатов выехал за границу как «племянник» Лебедя и его помощник в работе. В Хельсинки Лебедь передал его на попечение главного представителя ОУН в Финляндии Полуведько (агент ИНО ОГПУ), который, не зная об истинной роли Судоплатова, вообще предложил последнего убрать. Но решение таких вопросов не входило в его компетенцию.

Судоплатов вспоминал: «В Финляндии (а позднее и в Германии) я жил весьма скудно: у меня не было карманных денег и я постоянно ходил голодный. Полуведько выделял мне всего десять финских марок в день, а их едва хватало на обед — при этом одну монетку надо было оставлять на вечер для газового счётчика, иначе не работали отопление и газовая плита…

После двух месяцев ожидания в Хельсинки прибыли связные от Коновальца — Грибовский (Канцлер) из Праги и Андриевский из Брюсселя. Мы отправились в Стокгольм пароходом.

При посадке мне вручили фальшивый литовский паспорт…

В июне 1936 года прибыли в Берлин, и там я встретился с Коновальцем, который расспрашивал меня обо всём с большим пристрастием. Наша встреча проходила на квартире, находившейся в здании Музея этнографии и предоставленной ему германской разведслужбой. В сентябре меня послали на три месяца в нацистскую школу в Лейпциге. Во время учёбы я имел возможность познакомиться с оуновским руководством. Слушателей школы, естественно, интересовала моя личность. Однако никаких проблем с моей «легендой» не возникало.

Мои беседы с Коновальцем становились между тем всё серьёзнее. В его планы входила подготовка административных органов для ряда областей Украины, которые предполагалось освободить в ближайшем будущем, причём украинские националисты должны были выступить в союзе с немцами. Я узнал, что в их распоряжении уже имеются две бригады, в общей сложности около двух тысяч человек, которые предполагалось использовать в качестве полицейских сил в Галиции… и в Германии.

Оуновцы всячески пытались вовлечь меня в борьбу за власть, которая шла между двумя их главными группировками: «стариков» и «молодёжи». Первых представляли Коновалец и его заместитель Мельник, а «молодёжь» возглавляли Бандера и Костарев. Моей главной задачей было убедить их в том, что террористическая деятельность на Украине не имеет никаких шансов на успех, что власти немедленно разгромят небольшие очаги сопротивления. Я настаивал на том, что надо держать наши силы и подпольную сеть в резерве, пока не начнётся война между Германией и Советским Союзом, а в этом случае немедленно их использовать.

Особенно тревожили террористические связи этой организации, в частности, договорённость с хорватскими националистами и участие в убийстве югославского короля Александра и министра иностранных дел Франции Луи Барту. Для меня было открытием, что все эти террористы финансируются абвером — разведывательной и контрразведывательной службой вермахта. Полной неожиданностью явилась для меня и новость, что убийство польского министра генерала Перацкого в 1934 году украинским террористом Мацейко было проведено вопреки приказу Коновальца и стоял за этим Бандера, соперничавший с последним за власть. Бандера стремился к контролю над организацией, играя на естественной неприязни украинцев к Перацкому, который нёс ответственность за репрессии против украинского меньшинства в Польше. Коновалец рассказал мне, что к этому времени между Польшей и Германией был подписан договор о дружбе, так что немцев никоим образом не устраивали любые враждебные акции по отношению к полякам. Они были так взбешены, что выдали Бандеру, скрывавшегося в Германии».

В доверие к Коновальцу Павел Анатольевич сумел войти, передав ему однажды содержимое одного конфиденциального разговора.

«Как-то Костарев и ещё несколько молодых украинских националистов, слушателей нацистской партийной школы, стали говорить, что Коновалец слишком стар, чтобы руководить организацией, и его следует использовать лишь в качестве декоративной фигуры. Когда они спросили моё мнение, я возмущённо ответил:

— Да кто вы такие, чтобы предлагать подобное? Наша организация не только полностью доверяет Коновальцу, но и регулярно получает от него поддержку, а о вас до моего приезда сюда мы вообще ничего не слышали.

Когда я рассказал об этом Коновальцу, лицо его побледнело. Позже Костарев был уничтожен. Не думаю, что это случайное совпадение».

Удивительно, но Судоплатов каким-то образом сумел обаять лидера ОУН. Кто знает, сыграли в этом роль его подготовка в Москве или какие другие качества, но всё-таки это произошло. Коновалец привязался к нему и взял под свою опеку. Он очень часто брал Судоплатова погулять по городу. Один раз даже сводил Павла Анатольевича на спектакль в Берлинскую оперу.

Особое расположение Коновальца подтверждает предложение к Судоплатову сопровождать его в инспекционной поездке в Париж и в Вену.

«Во время нашего пребывания в Париже Коновалец пригласил меня посетить вместе с ним могилу Петлюры, после разгрома частями Красной Армии бежавшего в столицу Франции, где в 1926 году он и был убит. Коновалец боготворил этого человека, называя его «нашим знаменем и самым любимым вождём». Он говорил, что память о Петлюре должна быть сохранена. Мне было приятно, что Коновалец берёт меня с собой, но одна мысль не давала покоя: на могилу во время посещения положено класть цветы. Между тем мой кошелёк был пуст, а напоминать о таких мелочах Коновальцу я не считал для себя возможным. Это было просто бестактно по отношению к человеку, занимавшему столь высокое положение, хотя, по существу, заботиться о цветах в данном случае надлежало ему, а не мне. Что делать? Всю дорогу до кладбища меня продолжала терзать эта мысль.