1921 год становится в судьбе Павла Судоплатова поистине переломным. Комиссар дивизии Упит обратил внимание на смышлёного и образованного паренька и предложил ему поехать учиться на курсы политработников в Киев. Но в дело вмешался «его величество Случай», хотя случайность — это всего лишь незапланированная закономерность.
В июле 1921 года в засаду, устроенную украинскими националистами, попали сотрудники Особого отдела 44-й дивизии, и многие из них погибли. Учитывая происхождение, образование, Судоплатову была предложена вначале должность телефониста, а затем шифровальщика. Так — после диверсионной операции противника — началась его служба в органах ВЧК — ГПУ — О ГПУ — НКВД — НКГВ — МГБ.
«В дивизии, в которой я служил, вместе с нами сражались поляки, австрийцы, немцы, сербы и даже китайцы. Последние были очень дисциплинированными и сражались до последней капли крови. Борьба шла жестокая, и случалось, что целые деревни оказывались уничтоженными украинскими националистами и бандформированиями: всего в ходе Гражданской войны в Украине погибло свыше миллиона человек.
Опыт, приобретённый при выполнении обязанностей телефониста, а затем шифровальщика, оказался бесценным. Я печатал документы с грифом “секретно” и расшифровывал телеграммы, которые мы получали непосредственно от главы ВЧК Феликса Дзержинского из Москвы.
…Дивизия была переведена в Житомир. Главной задачей нашего особого отдела была помощь местному ЧК в проникновении в партизанское подполье украинских националистов, руководимое Петлюрой и Коновальцем. Их вооруженные банды устраивали диверсии против органов Советской власти на местах».
Осенью 1922 года Судоплатова переводят служить в пограничные войска, вначале в погранотделение города Из-яслав, а затем на Славутинский погранпост. Именно здесь Судоплатов соприкасается с особо секретными операциями разведки. Режим особой секретности был обусловлен тем, что по условиям мирного договора от 18 марта 1921 года между РСФСР и Польшей стороны обязались не создавать и не поддерживать организации, имеющие целью вооруженную борьбу с подписантом. Однако нелегальная боевая работа диверсионно-террористического характера на территории Западной Белоруссии и Западной Украины продолжалась. В данном случае политической задачей являлось воссоединение Западной Украины и Западной Белоруссии с Россией.
Операции Разведупра по активной разведке были тщательно законспирированы, в том числе от пограничников и местных органов ВЧК — ОПТУ, и были свёрнуты только в 1925 году по решению высшего военно-политического руководства СССР. Славутинскому погранпосту в этой тайной войне отводилась далеко не последняя роль. Павел, наблюдавший за молчаливыми людьми в гражданской одежде, мог понимать, что принимает участие в обеспечении совершенно секретных операций.
В начале сентября 1923 года Судоплатов подаёт рапорт об увольнении. Основной причиной такого поступка могла быть физическая, но главное — психологическая усталость юноши, которому к тому времени исполнилось всего 16 лет.
Другая причина заключалась в сокращении чекистского аппарата после окончания Гражданской войны, но это также связано с возрастом Павла. Рапорт молодого пограничника удовлетворили, и он вернулся домой в Мелитополь. Он поступает на службу в аппарат Мелитопольского окружного комитета Ленинского Коммунистического союза молодёжи Украины (ЛКСМУ). В 1924 году его направляют секретарём комсомольской ячейки в село Ново-Григорьевка Запорожской области. С января 1925 года Судоплатов — секретарь ячейки ЛКСМУ завода имени В.В. Воровского в Мелитополе. А в феврале того же года окружной комитет комсомола рекомендует «товарища Судоплатова» на работу в органы ОШУ. Впереди у Павла Анатольевича интересная и сложная работа в органах госбезопасности.
Итак, в феврале 1925 года в возрасте семнадцати лет Павел Судоплатов возвращается на службу в органы государственной безопасности — Мелитопольский окружной отдел ГПУ УССР. До 1927 года Судоплатов занимался обработкой оперативной информации, составлением отчётов, сводок и других справочных данных секретного характера.
В феврале 1928 года Павел вступает в ряды Всесоюзной Коммунистической партии большевиков — ВКП(б). (Партия получила новое название — Всесоюзная Коммунистическая партия (большевиков) на XIV съезде в 1925 году в связи с образованием СССР.)
В августе 1928 года Судоплатов получает очередное повышение и переводится в столицу тогдашней Украины г. Харьков на должность помощника уполномоченного секретного отделения Харьковского окротдела ПТУ УССР. В 1930-х годах П.А. Судоплатова переводят в центральный аппарат ПТУ УССР на должность помощника уполномоченного Отдела информации и политического контроля.
В 1932 году Судоплатов был переведён в Москву на должность старшего инспектора Отдела кадров ОПТУ. В это время он знакомится с начальником ИНО ОГЛУ А.Х. Артузовым и его заместителем А.А. Слуцким. В 1933 году Судоплатов переходит на оперативную работу в разведке. Это ещё один поворотный момент в его судьбе.
Назначение на оперативную работу в Иностранном отделе являлось далеко не таким простым. Противник, с которым отныне поручалось иметь дело Судоплатову, был хитёр и коварен. К 1933 году в среде украинских националистов произошли существенные изменения. С 1923 по 1928 год Украинская военная организация в обмен на свои услуги получила от спецслужб Веймарской республики свыше 2 миллионов марок.
Украинские националисты установили с германскими спецслужбами самые тесные контакты. После прихода А. Гитлера к власти в Германии наметились контакты специальных структур ОУН — УНО с СД и гестапо. Естественно, что руководство немецких спецслужб планировало использовать украинских националистов в своих собственных интересах.
Для руководства деятельностью националистов в Западной Украине был создан специальный орган ОУН — Краевая экзекутива (КЭ). Постепенно этот орган под руководством
С.А. Бандеры стал фактически неподотчётным ОУН и превратился в самостоятельную организацию. Но оуновцы активно действовали не только против Польши, но и против Советского Союза с польской и чехословацкой территорий. Более того, оуновцы пытались проводить террористические акты против официальных советских представителей и на территории третьих стран.
Советские органы государственной безопасности вели против украинских националистов нелёгкую и жесткую борьбу. Чекисты отслеживали и неоднократно пресекали террористические акты украинских националистов против советских государственных деятелей.
Так например, осенью 1933 года была сорвана попытка покушения украинских националистов на наркома иностранных дел Советского Союза М.М. Литвинова, которое должно было состояться во время его прибытия в Соединенные Штаты Америки.
Благодаря действиям нелегального резидента ИНО ОПТУ И.Н. Каминского и легального резидента ИНО в США В.Ш. Эльмана этот план был своевременно раскрыт. В итоге переговоры Литвинова с президентом США Ф. Рузвельтом прошли успешно, и 18 ноября 1933 года между СССР и США были установлены дипломатические отношения.
Однако действовать на опережение советской разведке удавалось не всегда. 21 октября 1933 года в консульстве СССР во Львове оуновский боевик Н. Лемек совершил террористический акт против сотрудника внешней разведки А. Майкова, работавшего в Польше в качестве дипломата. На одном из приёмов террорист подошёл к дипломату и в упор расстрелял его из пистолета.
По распоряжению военно-политического руководства СССР в органах госбезопасности началась разработка активных мер по нейтрализации террористических акций ОУН.
Тем временем в органах государственной безопасности произошла очередная глобальная перестановка. 10 июля 1934 года постановлением ЦИК СССР был образован Народный комиссариат внутренних дел СССР, с включением в него аппаратов ОГПУ и НКВД РСФСР. Наркомом назначен Г.Г. Ягода. На базе ОГПУ создаётся Главное управление государственной безопасности (ГУГБ) НКВД СССР. Его куратором стал Я.С. Агранов.
Исполняя распоряжение партии, руководство Иностранного отдела ГУГБ приняло решение о внедрении в среду украинских националистов своего сотрудника. Летом 1934 года выбор был сделан в пользу Павла Судоплатова.
После восьми месяцев обучения Судоплатов был направлен в свою первую зарубежную командировку в сопровождении Лебедя, «главного представителя» ОУН в Украине, а в действительности нашего тайного агента на протяжении многих лет. Лебедь стал для советской разведки ключевой фигурой в борьбе с бандитизмом в Украине в 20-х годах. Его репутация в националистических кругах за рубежом оставалась по-прежнему высокой: Коновалец рассматривал своего представителя как человека, способного провести подготовительную работу для захвата власти ОУН в Киеве в случае войны. От Лебедя, которому нами был разрешен выезд на Запад в 20-х и 30-х годах по нелегальным каналам, нам и стало известно, что Коновалец лелеял планы захвата Украины в будущей войне.
Куратором и одним из основных наставников П.А. Судоплатова в период его подготовки к нелегальной заграничной командировке стал опытный разведчик П.Я. Зубов. Этот человек станет одним из ближайших помощников П.А. Судоплатова во время Великой Отечественной войны.
Первоначальный курс обучения начинающий нелегал закончил в марте 1935 года. В это же время его жена Эмма была переведена в Иностранный отдел НКВД и также прошла специальный курс обучения. В будущей операции её планировалось использовать в качестве связной в Западной Европе между Павлом и Центром. По легенде, связная была студенткой из Женевы. Сам Павел выехал за границу под именем молодого украинского националиста Павла Анатольевича Яценко.
В середине апреля 1935 года Судоплатов выехал в Финляндию в сопровождении Лебедя, который, переправив «племянника» за границу, вернулся через Москву в Харьков.
В период пребывания в Хельсинки Судоплатов находился под опекой «легального» резидента в Финляндии Б.А. Рыбкина («Кин») и его помощницы (впоследствии супруги) З.И. Воскресенской («Ирина»). Эти выдающиеся разведчики внесли также свою лепту в оперативную подготовку молодого разведчика. В это время З.И. Воскресенская в Норвегии координировала работу нелегальной разведывательнодиверсионной группы Э.Ф. Волльвебера («Антон»).