1921 год стал переломным в жизни Павла Судоплатова.
В политотделе 44-й стрелковой дивизии обратили внимание на молодого бойца с оконченным начальным образованием, и предложили ему поступить на ускоренные курсы политработников в Киеве.
— Путишь инструктором политоттела, — говорил комиссар Упит. — Путишь рапотать с пойцами, вести культурно-массовую рапоту.
Павел согласился, но непредвиденные обстоятельства спутали эти планы. Бойцы Особого отдела дивизии попали в засаду, устроенную украинскими националистами, и понесли значительные потери. В Особом отделе срочно требовалось заменить погибших телефониста и шифровальщика. Было принято решение направить на их место Павла Судоплатова, как наиболее подготовленного для этой должности.
«Так я был послан на работу в органы безопасности. Это и было началом моей службы в ВЧК-КГБ», — позже напишет Павел Анатольевич.[13]
В Особом отделе его встретили немногословные, суровые люди. Окинули оценивающим взглядом, поинтересовались:
— Товарищ, почему к нам, может, пойдешь на трудовой фронт, бороться с разрухой?
— Разруху создают недобитые гады, значит, мое место в ЧК, — ответил Павел.
— Это ты верно, товарищ, про гадов заметил, а то разные умники, понимаешь, полагают, что разруха в башках, — похвалили его и зачислили в штат.
Поначалу четырнадцатилетний Павел занимался в Особом отделе, а затем в губотделе ГПУ на Волыни, различной технической работой. Был письмоводителем, регистратором, машинистом-систематизатором, но постепенно его стали привлекать к боевой чекистской работе.
В это время на Украине велась ожесточенная борьба против уголовного и политического бандитизма, основными кадрами которого были «кулаки, прошедшие школу гетманских «хлеборобских союзов» и петлюровских «управ», анархиствующие элементы из мелкой буржуазии местечек и городов и политически неустойчивая часть интеллигенции».[14] Сложность борьбы заключалась в том, что банды оперировали в приграничных районах с Польшей и Румынией и в случае необходимости уходили через границу в эти страны, где находили приют, заново вооружались и вновь проникали на Украину для продолжения разбоя и бесчинств. В одном из донесений штаба советских войск Украины и Крыма читаем, что «…тщательное рассмотрение состава и окраски банд Правобережья заставляет обратить внимание на тесную связь их с петлюровскими организациями за границей и продолжающееся проникновение на нашу сторону банд из-за кордона. Если бы не эти закордонные шайки, украинский разложившийся и переживший уже период своего наибольшего развития бандитизм был бы обречен на окончательное вымирание. Только заграничная поддержка агентами, руководителями и белогвардейским золотом питает бандитские шайки Правобережья».[15]
Местами наибольшего скопления бандитов являлся Матренинский монастырь и Холодный Яр — значительный лесной массив в Кременчугской губернии. В Холодном Яру находился так называемый Повстанком, который по директиве из Полыни готовил всеобщее восстание на Украине. В состав Повстанкома входили бывшие члены Центральной рады: Панченко, Дзигарь и Шапошник.
В одном из чекистских донесений того времени отмечалось: «За период с первого по пятнадцатое апреля с. г. (1921) в Кременчугской губернии наиболее активными уездами в отношении бандитизма являются Чигиринский, Черкасский, Александрийский, в которых в настоящий момент оперируют банды: Загородного — основное ядро 50 человек при 4 пулеметах, бандиты хорошо вооружены винтовками и обрезами — район действия Чигиринский уезд; Хмары и Черного, численностью 65–100 человек — район действия Золотоношский и Черкасский уезды; Голого — оперирует исключительно в районе Холодного Яра в количестве 47–50 человек, мелкие банды Кириченко, Иванова, Квочка Гаврила, Царенко, Добровольского, Савченко и Логенко, Ветки, Бондаренко, Клепача, Степового, Захарова, Ш гыля, Дергача, бывшего полковника Терещенко и др. Общее количество мелких банд 1500 человек».
Не менее сложной обстановка была и в других украинских губерниях. На Екатеринославщине оперировали банды Бровы и Каменюка общей численностью до 500 сабель. На Киевщине действовали банды Грызла, Цветковского, Мордалевича, Дороша, Яременко, Богатыренко, Цербалюка, Сгрука; на Полтавщине — банды Гонты, Христового, Матвиенко, Вояки, Штапы; на Подолыдине — банды Шепеля, Складного, Заболотного, Моргуля, Гранового, Салтиса. В Донбассе орудовало 18 банд общей численностью свыше 1000 сабель.