29 ноября 1918 года в Мелитополь вошла Добровольческая армия генерала Деникина. Первым ее действием стала мобилизация молодых людей в армию, которая натолкнулась на сопротивление населения. Даже расстрелы активных отказников не дали результата. Попытка провести мобилизацию в селах лишь спровоцировала народные волнения.
4 января 1919 года по постановлению Реввоенсовета Республики на базе войск Украинской советской армии был образован Украинский фронт под командованием Антонова-Овсеенко. Его войскам противостояли воинские формирования правительства украинской Директории[2], сменившей в ноябре 1918 года режим гетмана Скоропадского, войска генерала Деникина и Антанты[3], захватившие Крым и ряд южных губерний Украины.
В конце февраля 1919 года части Харьковской группы войск Украинского фронта перешли в наступление. В марте бойцы Украинского фронта вошли в Мелитополь. Им активно помогали подпольщики-большевики. Подавляющее большинство населения города встречало красноармейцев с ликованием. На улице Павел Судоплатов случайно познакомился с одним из организаторов большевистского подполья в городе, активным борцом за советскую власть Игнатом Васильевичем Булыгой, работавшим в местных механических мастерских. Это знакомство окончательно определило дальнейшую судьбу юноши.
С приходом красных Булыга возглавил боевой отряд, сформированный из рабочих механических мастерских, перед которым была поставлена задача поддерживать революционный порядок в городе и охранять важные городские объекты. Павел стал порученцем при командире. Целыми днями он носился по городу, передавая устные и письменные распоряжения Игната Булыги, часто даже ночевал в штабе, чтобы всегда быть у него под рукой.
Между тем войска Украинского фронта развивали наступление по двум направлениям: основные силы Киевской группы — на запад, Харьковской группы — на юг. Правда, не всегда им сопутствовал успех. Так, с серьезными трудностями столкнулись части Киевской группы в районе Коростеня, встретившись со скрытно переброшенными туда двумя дивизиями стрельцов Коновальца. Положение спасли 1-я Украинская советская дивизия Н. А. Щорса и ряд боеспособных частей, отозванных из Харьковской группы. К началу апреля положение в районе Коростеня было восстановлено.
В то же время Верховный совет Антанты, вынужденный признать бесперспективность дальнейшего пребывания французских экспедиционных сил на Украине, принял решение о их эвакуации морем. Вскоре войска Антанты ушли из Одессы, прихватив с собой 122 транспортных судна с награбленным имуществом. 6 апреля в Одессу вошли части Красной армии.