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