В феврале 1920 года Павел Судоплатов вновь вступил в ряды Красной Армии, на этот раз — в роту связи 123-й стрелковой бригады 41-й дивизии 14-й советской армии. В составе этого соединения он сражался во время советско-польской войны.

Это воинское подразделение участвовало в январе-феврале 1920 года в разгроме войск Главнокомандующего Вооруженными Силами Юга России Антона Ивановича Деникина в нижнем течении реки Днестр, затем в обороне Черноморского побережья и Днестра.

В апреле-июне 1920 года дивизия участвовала в боях с белополяками в районе среднего течения реки Днестр, а также в боях против банд петлюровского атамана Юрко Тютюнника; в июне-июле — вела наступлении в районе Волочиск — Кременец — Каменец-Подольский; в июле-августе — участвовала в форсировании рек Збруч, Серет, Золотая и Гнилая Липа и освобождении городов Теребовль, Чертков, Галич, Рогатин.

После отступления советских войск из-под Варшавы в августе-сентябре 1920 года 41-я дивизия отошла в район Каменец-Подольского, в районе которого участвовала в ликвидации петлюровских отрядов.

А 21 декабря 1920 года потерявшая в кровопролитных боях часть личного состава 41-я дивизия была сведена в бригаду и влита в 44-ю дивизию 12-й армии, а с января 1921 года вошла в состав Киевского военного округа под названием 44-я Киевской советской дивизии.

Это подразделение «специализировалось» на борьбе с антисоветскими националистическими формированиями. Например, зимой 1920–1921 года бойцы дивизии сражались с членами отрядов (численность 300–400 человек) атамана Ильи Струка. В апреле-июне 1921 года атаман еще громил советские учреждения и еврейские местечки на Киевщине. Главными «операциями» Струка тогда стали захваты речных пароходов, что курсировали по Днепру. Было захвачено более двадцати пароходов и столько же барж, буксиров, причем операции сопровождались зверским уничтожением пассажиров — евреев, коммунистов, красноармейцев. Последний раз «банда Струка» упоминается в документах в октябре 1922 года в связи с погромом в Мартыновской волости, в ходе которого было убито 80 евреев. В эти месяцы банда состояла всего из 30–50 человек.