Ударной силой Цупчрезкома был Особый отдел. Его задачи заключались в охране границ, ведении контрразведки, борьбе со шпионажем и вышеупомянутым бандитизмом. Для борьбы с крупными бандитскими соединениями использовались войска внутренней охраны (BOXP), Донецкая дивизия Ч К Украины, сформированная в феврале 1921 года, и части особого назначения (ЧОН). По инициативе М. В. Фрунзе создавались специальные летучие отряды, которые преследовали мелкие банды и уничтожали их, не давая им рассеяться. Особенно внимательно Фрунзе относился к личному составу этих отрядов. В своем приказе он требовал:
«Широко использовать для состава таких отрядов добровольцев, вполне отвечающих требованиям честного, отважного, предприимчивого бойца, привычного к партизанской работе. На подбор всего состава отряда и добровольцев и по назначению обратить особое внимание. Безусловно, необходимо самое широкое комплектование отрядов коммунистами, могущими внести идейный характер в ответственную работу летучих отрядов».
В июне 1921 года Кременчугскому губвоенсовещанию и Киевскому военному округу Фрунзе была послана следующая телеграмма: «Ввиду создания в Холодном Яре повстанческого штаба, предлагаю усилить в этом районе борьбу с бандитизмом с целью скорейшей его ликвидации, закрепляя ликвидацию соответствующей политработой. Реввоенсовету, командованию, КВО использовать для этого все имеющиеся в их распоряжении средства и установить теснейший контакт с Кремгубсовешанием».
К этому времени в Кременчугской губернии оперировали такие банды: объединенная банда Холодного Яра — атаманы Петренко, Деркач, Чучунак и Пономаренко; банда Нагорного действовала в районе островов на Днепре северо-восточнее пристани Бужин; в лесном районе к западу от м. Жаботина оперировала банда Овчаренко; в Цветнянском лесу — банда Железняка; в болотистых островах реки Тясьмин, в 8 км от Чигирина, находилась банда Бойко; в Черном лесу севернее Знаменки — банда Хвиля, а в Матусовском лесу — банда Черного Ворона.
В августе советские войска разгромили важнейшую опорную базу бандитов в Холодном Яру и Матренинском монастыре, уничтожили отряды Овчаренко, Нагорного, Железняка, Назара Стодоли. Преследуемый 24-м кавалерийским полком, отряд атамана Лихо переправился через Днестр и ушел в Румынию. Атаманы Мордалевич, Орлик, Цветковский, Лисица и Грозный добровольно сдались властям.
В Донецкой губернии, по данным штаба Донецкой дивизии: «… в июле (1921 г.). на территории Донбасса оперировало 18 банд общей численностью в 1042 сабли с 19 пулеметами. В августе количество банд возросло до 21, численность же их уменьшилась до 953 сабель с 30 пулеметами. С разгромом основного ядра банды Махно, бандитизм махновской окраски в Донбассе сразу же пошел на убыль и в сентябре в губернии осталось 16 банд с 548 саблями и 15 пулеметами. В дальнейшем численность бандитов стала быстро уменьшаться, в октябре в Донбассе осталось 11 банд с 383 саблями и 20 пулеметами, в ноябре 8 банд с 261 саблями и 13 пулеметами и в декабре организованных банд нет вовсе».
Помимо банд значительную опасность на Украине представляло петлюровское подполье. В мае 1921 года в Варшаве состоялось совещание петлюровских атаманов, на котором присутствовали Ю. Тютюнник, Удовиченко, Зеленский, Павленко, Безручко и др. От петлюровского правительства, реорганизованного в Тарновскую Раду, принимали участие Никовский, Прокопович, Пилипчук, Михайлов и др. На совещании обсуждался вопрос о том, какими средствами усилить повстанческие отряды на Украине и сохранить петлюровскую армию в Польше. 13 июня состоялось еще одно совещание, на котором, кроме петлюровцев, присутствовали Б. Савинков, Гнилорыбов, Философов, представители польского командования, французской и английской миссий. Вновь обсуждался вопрос об усилении повстанческого движения на Украине и в Белоруссии, о новом походе против страны Советов. Представители польского командования «обещали всяческое содействие петлюровцам. Незадолго до этого совещания Пилсудский, приехав в Станислав, в разговоре с Петлюрой заявил, что польское правительство окажет содействие петлюровцам оружием, амуницией, снаряжением и т. д. Он говорил о том, что сейчас, после 1920 г., польское правительство не может рисковать вторично своей армией для нового похода на Украину, но поддержка петлюровцам будет обеспечена. При участии польского командования был создан центральный повстанческий штаб во главе с петлюровским атаманом Ю. Тютюнником. Став начальником штаба, Тютюнник приехал в Варшаву к польскому командованию за инструкциями. Там же он получил указания и от представителей французской миссии, связался с представителями гетманских хлеборобов. На свидании с Савинковым Тютюнник договорился о том, чтобы действовать единым фронтом. Усиленными темпами шла подготовка новых петлюровских формирований».