К середине февраля 1920 года о Махно и его армии не было никаких сообщений. Возле тяжелобольного Махно остались несколько командиров и охрана. Красные части, которые сновали по махновским селам, нигде не находили повстанческих отрядов. Складывалось впечатление, что украинское село наконец покорилось, а повстанцы превратились в мирных хлебопашцев. Но 2 февраля 1920 года возле с. Успеновка 20 махновцев взяли в плен 100 красноармейцев, а 4 февраля Махно на несколько дней захватил Гуляйполе, которое накануне оставили основные силы красных карателей. В Гуляйполе Махно удалось напечатать несколько тысяч листовок, в которых он снова призвал крестьян к борьбе против большевиков. Крестьянам предлагалось создавать тайные отряды в каждом селе и готовиться к всеобщему восстанию.
6 февраля 1920 года командующий Юго-западным фронтом издал приказ по Эстонской дивизии: в кратчайший срок задавить махновцев «до полного уничтожения и стереть населенные пункты с лица земли». 8 февраля кавполк 42-й дивизии неожиданно напал на Гуляйполе и окружил махновский штаб. Махно сумел вырваться из окружения вместе с 50 всадниками, большая же часть его отряда была разгромлена. Батько с оставшимися в живых бойцами ворвался в Царевоконстантиновск, где разоружил роту красных и расстрелял всех пленных коммунистов. На протяжении последующих 10 дней махновцы гуляли по степи, пуская под откос эшелоны, уничтожая продотряды и красных агитаторов. Узнав, что в Пологах находится центр снабжения 42-й дивизии, махновцы напали на эту станцию, захватив 12 пушек и 10 пулеметов.
В это время группами по 10–20 человек к Махно начали примыкать его бывшие товарищи-повстанцы. Когда у Махно набралось 150 бойцов, махновцы вновь захватили Гуляйполе, взяв в плен 300 красноармейцев. Там же Махно начал формировать свою армию в составе 3 полков пехоты, полка кавалерии и пулеметного полка. Но вскоре на Гуляйполе напал усиленный кавалерийский полк красных. В первые минуты боя красные захватили махновский штаб в центре села и убили штабистов и брата Нестора — Савву (начальника снабжения армии), что дезорганизовало оборону. К тому же красные снова захватили всю махновскую артиллерию и канцелярию.
Когда продотряды добрались до отдаленных степных сел, настроение крестьянства вновь качнулось в сторону вооруженной борьбы против «совдепии». 1 марта махновцы выбили из Гуляйполя красный полк и стали хозяевами в селе. Махно принялся восстанавливать систему «свободных советов», однако приток крестьян в повстанческое войско был незначительным. В отряде Махно собралось около 1,5 тыс. повстанцев. 4 марта красные попытались овладеть ст. Гуляйполе, но их атака была отбита, хотя несколько полков Эстонской дивизии были разгромлены. Вскоре на махновцев были направлены части Латышской и 41-й дивизий, а также отдельный кавалерийский полк. 12 марта махновцев снова выбили из Гуляйполя. Но уже 20 марта Махно предпринял новое нападение на Гуляйполе. Через два дня он был выбит оттуда особой кавдивизией, специально созданной для борьбы против махновцев. Эта дивизия и несколько бригад 42-й дивизии закрепились в Гуляйполе, заблокировав базовый махновский район.