С Коновальцем у Судоплатова складывались неплохие отношения.

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

Центр решил воспользоваться этой возможностью, чтобы организовать встречу Судоплатову с его курьером. Согласно указанию из Москвы, Павлу надлежало по возможности выйти на такую встречу в Париже и позднее в Вене. Для этого он должен был дважды в неделю появляться между пятью и шестью вечера в определенном месте.

«В первое же своё появление на условленном месте, — рассказывал Павел Анатольевич, — я увидел собственную жену… Усилием воли мне удалось заставить себя удостовериться, что за мной нет никакой слежки, и лишь после этого я приблизился к Эмме. Мне сразу же стало совершенно ясно: место встречи выбрано крайне неудачно, так как сновавшая вокруг толпа не давала возможности проверить, есть ли за тобой наблюдение или нет».

П. Судоплатов информировал Эмму о положении дел в украинских эмигрантских кругах и о той значительной поддержке, которую они получали от Германии. Особенно любопытной показалась ей информация, касающаяся раздоров внутри ОУН.

После приезда Павла в Вену он отправился на место встречи, где и застал своего куратора и наставника по работе в Москве Зубова. Разведчик подробно информировал Зубова о деятельности Коновальца.

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

По окончании командировки П. Судоплатов вернулся в Москву. Вот как он потом вспоминал сам:

«Успешная командировка в Западную Европу изменила моё положение в разведке. О результатах работы было доложено Сталину и Косиору, секретарю ЦК Коммунистической партии Украины, а также Петровскому, председателю Верховного Совета республики. В кабинете Слуцкого, где я докладывал в деталях о своей поездке, меня представили двум товарищам: один из них был Серебрянский, начальник Особой группы при наркоме внутренних дел — самостоятельного и в то время мне неизвестного Центра закордонной разведки органов безопасности, — а другой, по-моему, Васильев, сотрудник секретариата Сталина. Ни того ни другого я прежде не знал».

Скорее всего, Павел Анатольевич имел в виду руководящего работника Коминтерна Б.А. Васильева. Он тесно сотрудничал с Иностранным отделом ГУГВ НКВД и Разведывательным управлением Штаба РККА.

Тем временем П. Судоплатов был назначен вначале оперуполномоченным, а затем помощником начальника 4-го отделения 7-го отдела (внешняя разведка). Весь 1937 год он неоднократно выезжал на Запад в качестве «курьера» оунов-ского подполья. Как прикрытие использовалась должность радиста на советском грузовом судне «Шилка».

После убийства С.М. Кирова в декабре 1934 года руководство страны принимает решение о применении мер физического воздействия к врагам партии и государства. В числе личных врагов Сталина числились и бывшие служащие советских учреждений за границей, такие как Г.З. Веселовский, оставшийся во Франции, или нелегальный резидент ИНО ОПТУ в Турции Г.С. Агабеков, бежавший в 1930 году из Стамбула в Марсель. В 1931 году он опубликовал в Нью-Йорке книгу под названием «ОПТУ: русский секретный террор». Книга Г.С. Агабекова стала смертным приговором для многих друзей Советского Союза. Только в Персии (Иран) в июле — августе 1932 года было арестовано более четырёхсот человек. В этой связи было принято решение о ликвидации предателя. Вскоре Агабеков был ликвидирован в Париже.

В июле 1937 года во Франции остался нелегал И.Г. Порецкий (Рейс), который направил в Москву письмо с критикой Сталина и проводимой им в Испании политике. Порецкий был крайне опасен в силу его информированности о нелегальных сетях ИНО ОПТУ. Он был ликвидирован сотрудниками ГУГБ во главе с С.М. Шпигелыласом.

Одной из наиболее известных операций внешней разведки является похищение в 1937 году руководителя Российского общевоинского союза Е.К. Миллера, сменившего на этом посту А.П. Кутепова. После того как во второй половине 1930-х годов Миллер через своего представителя в Берлине, генерала Лампе, установил тесные контакты со спецслужбами гитлеровской Германии, в Москве было принято решение о проведении операции по его похищению и вывозу в СССР. Ключевым звеном этой операции являлся бывший командир Корниловской дивизии, помощник Миллера по разведке генерал Н.В. Скоблин, который с 1930 года вместе со своей женой, известной певицей Н.В. Плевицкой, сотрудничал с советской разведкой.

22 сентября 1937 года по приглашению Н.В. Скоблина Миллер направился с ним на виллу под Парижем, где должна была состояться встреча «с представителями германских спецслужб». На самом деле на вилле Миллера поджидала оперативная группа внешней разведки, которая захватила его и через Гавр переправила на теплоходе в СССР. После проведённого в Москве следствия Миллер был предан суду и в 1939 году расстрелян. В операции по захвату Миллера участвовали советские разведчики В. Гражуль, М. Григорьев, Г. Косенко. Руководил операцией С.М. Шпигелылас.

Решение оуновцев поставлять Японии военную и экономическую информацию об СССР стала последней каплей, решившей судьбу лидера украинских националистов. В ноябре 1937 года П.А. Судоплатов удостоился двух аудиенций у Сталина. На второй из них вождь отдал личное распоряжение о ликвидации Е. Коновальца.

После получения приказа о ликвидации Коновальца Слуцкий, Шпигелылас и Судоплатов приступили к разработке вариантов операции. От предложения застрелить Коновальца отказались, поскольку он довольно часто приходил на встречу в сопровождении телохранителя. Было принято решение вручить Коновальцу взрывное устройство, замаскированное под небольшой подарок. Этот вариант давал возможность исполнителю заблаговременно покинуть место встречи.

Часовой механизм мины-ловушки приводился в действие автоматически — через полчаса после изменения упаковки из транспортного (вертикального) в боевое (горизонтальное) ожидался взрыв. Судоплатову следовало быть предельно осторожным и держать коробку строго в вертикальном положении. В случае ошибки или небрежности он сам мог стать жертвой своего «подарка». Он также не должен был попасть в руки врага живым: согласно приказу, ему следовало покончить с собой, для чего он получил карманный «вальтер» модели РРК.

«Шпигелылас провёл со мной более восьми часов, — писал Судоплатов, — обсуждая различные варианты моего ухода с места акции. Он снабдил меня сезонным железнодорожным билетом, действительным на два месяца на всей территории Западной Европы, а также вручил фальшивый чехословацкий паспорт и три тысячи американских долларов, что по тем временам было большими деньгами. По его совету я должен был обязательно изменить свою внешность после “ухода”».