Тем не менее в начале сентября 1923 года Судоплатов подал рапорт о переводе со службы на погранпосту в Мелитополь. Рапорт был удовлетворен. В конце месяца молодой пограничник Павел Судоплатов вернулся домой. Причиной этого была не только усталость от участия в боевых действиях, но и то, что в Украинском ГПУ, как и по всей стране, началось сокращение чекистского аппарата и резкое уменьшение его финансирования.
В родном городе Павел Судоплатов попал на работу в аппарат Мелитопольского окружкома Л КСМУ (в комсомол он вступил во время службы на границе). Вначале был заведующим информационного отдела окружкома и членом правления, затем — комендантом клуба рабочей молодежи. В 1924 году его направили секретарем сельской комсомольской ячейки в село Ново-Григорьевка Генического района Запорожской губернии, а в январе 1925 года — секретарем ячейки ЛКСМУ завода имени Воровского (бывшие механические мастерские Гольца) в Мелитополе.
В феврале того же года окружком комсомола направил Павла Судоплатова на работу в органы ОГПУ.
— Доверяем тебе, товарищ Судоплатов, беречь Советскую власть. Будь бдителен, зорок и беспощаден к врагам пролетариата, дави их своей мозолистой рукой без всякого снисхождения и жалости, — такими словами напутствовал его секретарь Мелитопольского окружкома ЛКСМУ.
Так Павел Судоплатов восстановил свой стаж чекистской работы, прерванный на полтора года. В 1925–1927 годах он — сводчик информационного отделения Мелитопольского Окружного отдела ГПУ, в 1928 году — помощник уполномоченного учетно-статистического отделения Мелитопольского окротдела, затем — младший оперативный работник в окружном отделе ОГПУ, отвечающий за работу с осведомителями, действовавшими в греческом, болгарском и немецких поселениях. Работа с осведомителями, в просторечии — стукачами, требовала от сотрудника большой выдержки и хладнокровия. Общение с подобным человеческим материалом было тяжелым и неприятным. Многие оперативники не выдерживали и подавали рапорт о переводе в другой отдел.
Павел Судоплатов был хладнокровен и выдержан. Оперативный материал, собранный им в ходе встречи с осведомителями, всегда представлял определенный интерес для органов госбезопасности. Что иногда вызывало раздражение непосредственного начальства Судоплатова, так это клички агентов — осведомителей.
— Товарищ Судоплатов, почему у ваших осведомителей такие дикие клички — Хряк, Дубина, Страхуил, Побелка Потолков какой-то… Что это такое? Неужели нельзя придумать что-нибудь более благозвучное, — сердилось начальство.
— Псевдонимы осведомители выбирают себе сами. Вмешиваться в этот процесс считаю невозможным и вредным для дела, — отвечал Судоплатов.
— Ну, хорошо, пускай будут дубинами, если им так хочется, — в конце-концов соглашалось начальство.
В 1928 году Павел Судоплатов получил повышение и был переведен в Харьков, тогдашнюю столицу Украины, где стал работать уполномоченным Информационного отдела ГПУ УССР.
Именно здесь, в Харькове, двадцатилетний Судоплатов встретил свою будущую жену — Эмму Карловну Каганову (Суламифь Соломоновну Кримкер), так же? как и он, служившую в органах госбезопасности.
В своих мемуарах Павел Анатольевич тепло вспоминал о подруге жизни:
«Она приехала на Украину из белорусского города Гомеля. Эмма была способной, и ей удалось поступить в гимназию, где для евреев существовала ограничительная норма. Она окончила несколько классов гимназии и позднее стала работать секретарем-машинисткой у Хатаевича, секретаря гомельской губернской организации большевиков. Когда ее начальника перевели в Одессу, где он возглавил партийную организацию, она последовала за ним. Именно в Одессе Эмма перешла в местное ГПУ. Ей поручили вести работу среди проживавших в городе немецких колонистов. Голубоглазая блондинка, она говорила на близком к немецкому идише и вполне могла сойти за немку.
В Харьков ее перевели за год до того, как я туда перебрался. Эмма занимала в ГПУ УССР более весомое положение, чем такой новичок, каким я тогда был. Как образованной и привлекательной женщине, к тому же начитанной и чувствовавшей себя вполне свободно в обществе писателей и поэтов, ей доверили руководить деятельностью осведомителей в среде украинской творческой интеллигенции — писателей и театральных деятелей. Мы встретились с ней на службе, и меня поразили ее красота и ум. Отец Эммы, сплавщик леса, умер, когда ей было всего десять лет. Она начала работать и одна содержала всю семью, где было восемь детей. Так что у нас с Эммой было много общего: и я, и она являлись опорой для семьи и должны были в силу обстоятельств рано повзрослеть (…). Для меня Эмма была идеалом настоящей женщины, и в 1928 году мы поженились, хотя официально зарегистрировали наш брак лишь в 1951 году».
