После освобождения города от белых в начале 1920 года Павел в качестве воспитанника полка РККА был определен помощником телеграфиста роты связи 123-й стрелковой бригады 41-й дивизии 14-й армии. С бригадой участвовал в боях на Украине и на Польском фронте. В мае 1921 года юный красноармеец был назначен письмоводителем Особого отдела дивизии. После окончания курсов подготовки политработников Судоплатов служил в Житомирско-Волынском и в Харьковском губернских отделах ГПУ. С сентября 1923 года находился на комсомольской работе в Мелитополе.
В феврале 1925 года окружной комитет ЛКСМУ направил Судоплатова на работу в Мелитопольский окружной отдел ГПУ. Являясь младшим оперработником учетно-статистического отделения, он поддерживал связь с агентурой, действовавшей в греческом, болгарском и немецком поселениях. В августе 1928 года переведен на должность уполномоченного секретно-политического отдела ГПУ УССР в Харькове. Одновременно учился на рабфаке ГПУ. В 1928 году был принят в члены ВКП(б).
В феврале 1932 года Судоплатов был переведен в Москву, в центральный аппарат ОГПУ. Работал инспектором, а затем – старшим инспектором отдела кадров ОГПУ, курировал Иностранный отдел. С учетом большого чекистского опыта в апреле 1933 года Судоплатов был переведен на работу в Иностранный отдел. С нелегальных позиций выезжал в спецкомандировки в Германию и Финляндию.
В 1935 году под прикрытием представителя украинского антисоветского подполья Судоплатов был внедрен в руководство ОУН в Берлине. Завоевав расположение лидера ОУН полковника Евгена Коновальца, разведчик вошел в его ближайшее окружение и сопровождал в инспекционные поездки в Париж и Вену. 23 августа 1938 года в Роттердаме Судоплатов ликвидировал лидера украинских националистов.
В ноябре – декабре 1938 года Павел Анатольевич исполнял обязанности начальника внешней разведки. Затем возглавлял испанское отделение ее центрального аппарата. 10 мая 1939 года Судоплатов был назначен заместителем начальника внешней разведки. В этой должности он руководил операцией «Утка», связанной с физическим устранением Льва Троцкого, которая была успешно завершена 20 августа 1940 года в Мексике.
«Нам удалось не просто обезглавить троцкистское движение, – подчеркивал в своих воспоминаниях генерал Судоплатов, – но и предопределить его полный крах… Мне совершенно ясно, что сегодняшние моральные принципы не совместимы с жестокостью, характерной и для периода борьбы за власть, которая следует за революционным переворотом, и для Гражданской войны. Сталин и Троцкий противостояли друг другу, прибегая к преступным методам для достижения своих целей, но разница заключается в том, что в изгнании Троцкий противостоял не только Сталину, но и Советскому Союзу как таковому. Эта конфронтация была войной на уничтожение».
После очередных преобразований, последовавших в разведке в феврале 1941 года, генерал Судоплатов стал заместителем начальника 1-го (разведывательного) управления НКГБ СССР. В годы Великой Отечественной войны он одновременно являлся начальником 4-го управления НКВД – НКГБ СССР. Это управление было создано в январе 1942 года для руководства зафронтовой работой органов госбезопасности и Отдельной мотострелковой бригадой особого назначения (ОМСБОН). Большинство руководящих должностей в управлении занимали откомандированные в него сотрудники внешней разведки.
На управление возлагались задачи по организации в крупных городах на оккупированных территориях нелегальных резидентур, внедрению агентуры в оккупационные военные и административные органы, по подготовке и заброске в тыл врага разведывательно-диверсионных отрядов и групп, организации резидентур в районах, находящихся под угрозой захвата, обеспечению групп специального назначения и агентов оружием, средствами связи и документами. Помимо решения этих задач сотрудники управления сыграли ведущую роль в проведении многих оперативных игр с противником, в частности, – операций «Монастырь» и «Березино».
Отдельная мотострелковая бригада особого назначения включала в себя два полка. Местом формирования бригады стал Центральный стадион «Динамо». Помимо чекистов в бригаду входили свыше 800 спортсменов, среди которых было немало заслуженных мастеров спорта, известных тренеров, чемпионов и рекордсменов СССР, Европы и мира. Общая численность бригады составляла в тот период 10 500 человек. В первые годы войны не каждая стрелковая дивизия могла сравниться с ней по численности и по обученности.
На подмосковном стрельбище «Динамо» вновь созданные оперативные группы особого назначения под руководством специалистов 4-го управления изучали минное дело, подрывную технику противника, овладевали тактикой действий небольшими группами, приемами ведения ночной разведки, топографией, радиоделом, совершали марш-броски, прыжки с парашютом. Короче, учились всему, что необходимо на войне.