В феврале 1925 г. по направлению окружкома комсомола был принят на работу в Мелитопольский окружной отдел ГПУ сотрудником информационного отделения, помощник уполномоченного учетно-статистического отдела, младший оперативный работник, ведал агентурной работой в греческом, болгарском и немецком поселениях. С августа 1928 г. уполномоченный секретно-политического отдела Харьковского окружного отдела, уполномоченный информационного отдела ГПУ УССР в Харькове. Одновременно в 1928–1930 г. заочно учился на рабфаке. В 1928 г. вступил в ВКП(б).
В феврале 1932 г. переведен в центральный аппарат ОГПУ. Инспектор, старший инспектор 1-го отделения Отдела кадров ОГПУ, курировал кадры ИНО. С 1933 г. в аппарате ИНО ОГПУ, оперуполномоченный 5-го, затем 8-го отделений. С октября 1933 г. в резерве Отдела кадров ОГПУ в связи со специальной командировкой за рубеж. По возвращении в СССР с ноября 1934 г. оперуполномоченный 7-го отделения ИНО ГУГБ НКВД.
В 1935 г. под видом представителя украинского антисоветского подполья под псевд. «Андрей» внедрен в руководство ОУН в Берлине. Учился в специальной партийной школе НСДАП в Лейпциге. Завоевал доверие лидера ОУН полковника Е. Коновальца, вошел в его ближайшее окружение и сопровождал в инспекционных поездках в Париж и Вену. В 1937–1938 гг. «Андрей» выезжал нелегальным курьером в ряд стран Западной Европы под прикрытием должности радиста грузового судна. 23 августа 1938 г. по личному поручению И. В. Сталина осуществил в Роттердаме (Нидерланды) ликвидацию Е. Коновальца, передав ему коробку конфет с заложенной в нее бомбой.
По возвращении в СССР оперуполномоченный ИНО, затем помощник начальника отделения 7-го отдела ГУГБ НКВД СССР, и.о. помощника начальника 4-го (испанского) отделения 5-го отдела ГУГБ. В ноябре-декабре 1938 г. после ареста 3. И. Пассова и С. М. Шпигельглаза исполнял обязанности начальника 5-го отдела ГУГБ НКВД.
В конце декабря 1938 г. был отстранен от работы и исключен первичной парторганизацией отдела из ВКП(б) за «связь с врагами народа». Благодаря вмешательству руководства НКВД решение не было утверждено парткомом наркомата.
В январе 1939 г. Судоплатов — зам. начальника 4-го отделения. С мая 1939 г. зам. начальника 5-го отдела ГУГБ НКВД СССР. Руководил подготовкой операции «Утка» (ликвидация Л. Д. Троцкого), осуществленной 20 августа 1940 г. в Мексике Л. А. Эйтингоном и Р. Меркадером. С февраля 1941 г. зам. начальника 1-го (разведывательного) управления НКГБ СССР. С июля начальник Особой группы при наркоме внутренних дел СССР, с октября 1941 г. — 2-го отдела НКВД СССР. Одновременно с ноября 1941 по июнь 1942 г. зам. начальника 1-го управления НКВД.
С января 1942 г. начальник 4-го управления НКВД СССР, созданного на базе 2-го отдела. Руководил партизанскими и разведывательно-диверсионными операциями в ближнем и дальнем тылу противника, координировал работу агентурной сети на территории Германии и стран ее союзников, с ноября 1942 г. по совместительству зам. начальника 1-го управления НКВД СССР. С мая 1943 г. начальник 4-го управления НКГБ СССР.
С февраля 1944 г. начальник группы «С» при наркоме внутренних дел СССР, руководил переводом и обобщением агентурных материалов по атомной проблеме. Одновременно с мая по август 1945 г. начальник отдела «Ф» НКВД СССР (работа на территории стран, освобожденных Красной Армией от противника, сбор информации от граждан СССР, побывавших в плену или интернированных в странах Европы). В 1945–1947 гг. под именем П. Матвеева и прикрытием должности советника НКИД/ МИД участвовал в подготовке и проведении конфиденциальных переговоров наркома/министра иностранных дел СССР В. М. Молотова с чрезвычайным и полномочным послом США в СССР А. Гарриманом.
С сентября 1945 г. начальник созданного на базе группы «С» самостоятельного отдела «С» НКВД-НКГБ СССР и одновременно начальник Объединенного разведывательного бюро Специального комитета при СНК-СМ СССР по проблеме № 1 (создание атомного оружия): координировал обеспечение разведывательными материалами руководителей и ведущих ученых советского ядерного проекта; по совместительству начальник отдела «К» НКГБ СССР, в обязанности которого входило оперативное обслуживание атомных специальных объектов, а также начальник Особого бюро — информационно-аналитической службы при наркоме внутренних дел, позднее подчинявшейся министру госбезопасности СССР. После образования в марте 1946 г. МГБ СССР совмещал должности руководителя 4-го управления и отдела «С».