В 1935 находился на нелегальной разведывательной работе за границей (Андрей). Для выявления антисоветских планов украинских националистов, их агентуры и диверсантов на Украине, связей ОУН с иностранными разведками, под прикрытием представителя украинского антисоветского подполья был внедрен в руководство ОУН в Берлине. Андрею удалось попасть на учебу в специальную партийную школу нацистской партии в Лейпциге. Завоевав расположение лидера и основателя прогерманской фашистской организации украинских националистов полковника Е. Коновальца, разведчик вошел в его ближайшее окружение, сопровождал его в инспекционных поездках в Париж и Вену.
В 1937-1938 годах Андрей выезжал в Западную Европу в качестве нелегального курьера под прикрытием радиста грузового судна. 23 мая 1938 года по поручению И. Сталина в Роттердаме осуществил ликвидацию лидера ОУН Е. Коновальца.
С сентября 1938 года Судоплатов П. А. исполнял обязанности помощника начальника 4-го отделения 5-го отдела ГУГБ. После ареста руководителей разведки 3. Пассова и С. Шпигельглаза, других старших офицеров отдела в ноябре-декабре 1938 года исполнял обязанности начальника 5-го отдела ГУГБ НКВД — внешней разведки.
В декабре 1938 года был назначен помощником начальника Испанского отделения ИНО, однако уже в конце месяца его отстранили от дел. «За связь с врагами народа» в руководстве разведки был исключен первичной организацией отдела из ВКП(б). Но благодаря вмешательству руководства НКВД это решение не было утверждено парткомом наркомата.
16 января 1939 года утвержден заместителем начальника 4-го отделения 5-го отдела ГУГБ, а с 10 мая этого же года — заместителем начальника внешней разведки НКВД СССР. С 1939 года руководил подготовкой операции «Утка» (ликвидация Л. Троцкого), успешно осуществленной в Мексике 20 августа 1940 года Л. Эйтингоном и Р. Меркадером-дель-Рио.
26 февраля 1941 года решением Политбюро ЦК НВКП(б) П. А. Судоплатов назначается заместителем начальника Разведывательного управления только что созданного Наркомата Госбезопасности СССР.
После начала Великой Отечественной войны, с 26 июня 1941 года по совместительству он возглавил Штаб по ликвидации вражеских парашютных десантов и диверсионных групп. Тогда же был назначен заместителем начальника Центрального штаба истребительных батальонов НКВД СССР.
5 июля 1941 года П. А. Судоплатов был утвержден начальником Особой группы при наркоме внутренних дел СССР (Андрей), 3 октября 1941 года — 2-го отдела НКВД СССР. А с 30 ноября 1941 года по 1 июля 1942 года он одновременно являлся и заместителем начальника 1-го (разведывательного) Управления НКВД СССР.
