Затем последовало пребывание в Стокгольме, затянувшееся на несколько недель. Местный представитель ОУН продолжил тщательное изучение Павла. Он детально расспрашивал разведчика о «дяде» и о жизни на Украине. Убедившись, что Павел на самом деле является тем, за кого себя выдает, представитель Коновальца проникся к нему доверием и проинформировал об этом Берлин.
Итак, проверка в Стокгольме завершилась. Поставленная перед нелегалом Судоплатовым задача по внедрению в ряды борцов за «самостийную Украину» была успешно решена. Впереди разведчика ждали Германия и встреча с лидером ОУН Евгением Коновальцем.
В июне 1936 года Судоплатов прибыл из Стокгольма в Берлин и был представлен Коновальцу. Рассказывая о их первой встрече, санкт-петербургский писатель Виктор Степаков отмечал: «Встреча с лидером ОУН состоялась на конспиративной квартире, расположенной в здании Музея этнографии. Павел внутренне готовил себя к ней, проигрывал различные варианты, но Коновалец спутал все карты. Он встретил Судоплатова с распростертыми объятиями и напыщенными словами.
— Рад, рад приветствовать на дружественной германской земле племянника моего боевого соратника, ведущего борьбу за свободу неньки Украйны!
— Хай живе вильна Украйна! — с ходу подыграл “племянник”.
Коновалец был в восторге».
Разведчику удалось установить с лидером ОУН неплохие личные отношения. В сентябре 1936 года Павла направили на учебу на три месяца в специальную нацистскую партийную школу в Лейпциге. Во время учебы он имел возможность познакомиться с некоторыми представителями руководства ОУН. «В общении со своими коллегами по нацистской партийной школе, — рассказывал позже Судоплатов, — я держался абсолютно уверенно и независимо: ведь я представлял головную часть их подпольной организации на Украине, в то время как они являлись всего лишь эмигрантами, существовавшими на немецкие подачки. Я имел право накладывать вето на их предложения, поскольку выполнял инструкции своего “дяди”».
Между тем систематические встречи Павла с Коновальцем продолжались, их беседы раз за разом становились все серьезнее. Судоплатов выяснил планы Коновальца по подготовке административных органов для ряда областей Украины, которые предполагалось «освободить» в ближайшее время с помощью немцев. Также разведчику стало известно, что в распоряжении Коновальца уже имеются две бригады бойцов общей численностью около двух тысяч человек. Удалось узнать о подготовке оуновцами ряда террористических актов в европейских странах и о том, что эта подготовка финансируется разведкой и контрразведкой вермахта.
Со своей стороны Судоплатов пытался убедить Коно-вальца в том, что террористическая деятельность ОУН на Украине не имеет никаких шансов на успех, так как власти немедленно разгромят небольшие очаги сопротивления. Он настаивал на том, что надо держать все силы и подпольную сеть в резерве, пока не начнется война между Германией и Советским Союзом, и только в этом случае их использовать.
Коновалец с каждым днем относился к Судоплатову все лучше и доверял все больше. Их отношения постепенно перерастали в «дружеские».
Коновалец настолько привязался к Павлу, что даже предложил, чтобы он сопровождал его в инспекционной поездке в Париж и Вену с целью проверки положения дел в украинских эмигрантских кругах, поддерживавших лидера ОУН. Поездку щедро оплачивали немцы. В Париже они находились три недели.
Во время пребывания в Париже Коновалец пригласил Павла посетить вместе с ним могилу Симона Петлюры, который после разгрома его войск частями Красной армии бежал в столицу Франции, где в 1926 году был убит. Позже Судоплатов рассказывал: «Коновалец боготворил этого человека, называя его “нашим знаменем и самым любимым вождем”. Он говорил, что память о Петлюре должна быть сохранена. Мне было приятно, что Коновалец берет меня с собой, но одна мысль не давала покоя: на могилу во время посещения положено класть цветы. Между тем мой кошелек был пуст, а напоминать о таких мелочах Коновальцу я не считал для себя возможным. Это было бы просто бестактно по отношению к человеку, занимавшему столь высокое положение, хотя, по существу, заботиться о цветах в данном случае надлежало ему, а не мне. Что делать? Всю дорогу до парижского кладбища Монпарнас меня продолжала терзать эта мысль.
Мы прошли через все кладбище и остановились перед скромным надгробием на могиле Петлюры. Коновалец перекрестился, я последовал его примеру. Некоторое время мы стояли молча, затем я вытащил из кармана носовой платок и завернул в него горсть земли с могилы.
— Что ты делаешь?! — воскликнул Коновалец.
— Эту землю с могилы Петлюры я отвезу на Украину, — ответил я, — мы в его память посадим дерево и будем за ним ухаживать.
Коновалец был в восторге. Он обнял меня, поцеловал и горячо похвалил за прекрасную идею. В результате наша дружба и его доверие ко мне еще более укрепились».