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