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