В начале января 1919 года Махно отправил отряд Петренко (800 бойцов) на север Екатеринославщины. За Павлоград и Лозовую махновцы вели ожесточенные бои с частями армии УНР. Большевистский отряд разоружил махновцев и арестовал Петренко. После этого Махно направил против красных довольно большой отряд под командованием брата Петренко, который освободил арестованного брата и разогнал большевистский штаб. Наступление махновцев против отрядов немецких колонистов, организованных в добровольческую Егерскую бригаду, сложилось неудачно.

3—4 января 1919 года на вокзале ст. Пологи состоялся повстанческий съезд, на который прибыли 40 делегатов от отрядов и местного населения. Съезд высказался за создание «свободных советов», которые действовали бы без нажима со стороны военных или партийных деятелей. Под власть Советов переходило разделение земли и сельскохозяйственного инвентаря, они распоряжались землей имений. Съезд избрал оперативный штаб армии — высший военный орган фронта и тыла. Махно оставался командующим всей армией. Штаб должен был слить отряды в полки и сформировать новые части. Сложно было ограничить самоуправство атаманов местных отрядов, которые не желали подчиняться штабу. Съезд вооружил штаб директивой о том, что все отряды, не подчиняющиеся решению штаба, подлежат разоружению, а их командиры будут отданы под общеповстанческий суд.

Махновский фронт подразделялся на 4 основных участка. Было создано 5 повстанческих полков имени батька Махно, «черная сотня» — охрана Махно, конный отряд Щуся. Всего махновское войско насчитывало 8—10 тыс. штыков.

В конце декабря 1918 года части Добровольческой армии (до 5 тыс. бойцов) высадились в Геническе, Мариуполе, Бердянске и захватили побережье Азовского моря. К Добровольческой армии присоединились белогвардейские части Крымско-Азовской добровольческой армии, изгнанные из Крыма в Мелитополь, и Егерская бригада самообороны немецких колонистов (всего 5 тыс. штыков). В середине 1919 года белые продвинулись в «свободный район». Оборона Гуляйполя стала наиболее героическим эпизодом махновского движения. Несколько раз Гуляйполе переходило из рук в руки. Не имея оружия, резервные махновские отряды шли в бой с вилами, копьями, топорами. Махновское командование решило любой ценой отстоять «свободный район». Во время боев за село погибло около 500 махновцев. Повстанцев белые в плен не брали, а вешали вдоль дорог или расстреливали в балках. Белые казнили 20 жителей села, в том числе и брата Нестора Карпа. Махно пообещал односельчанам мстить белым, где бы они ни были.

23 января неподалеку от фронта в с. Б. Михайловка открылся первый съезд крестьян и повстанцев «свободного района». На съезде присутствовало около 100 делегатов. Махно не было на этом съезде, так как он находился на передовой. Съезд принял решение о мобилизации в армию Махно всех фронтовиков, одобрил резолюцию в поддержку махновского движения и постановил создать в районе «свободный совет». Махно во главе тысячи повстанцев пошел в наступление на ст. Гуляйполе. По колено в снегу батько шел в первых рядах наступающих, подбадривая их крепкими словечками. В боях 27–28 января махновцы отбили Гуляйполе у белых, но бои на южной околице села и за Пологи продолжались еще 10 дней.

21 января красные части Павла Дыбенко захватили Синельниково и послали махновцам телеграмму с предложением о переговорах относительно военного союза. Части Дыбенко составляли тогда 4 тыс. пехотинцев при 50 пулеметах и 18 пушках. Но им удалось 26 января выбить из Екатеринослава отряды армии УНР. Дыбенко и махновский представитель Чубенко встретились в Синельниково и составили соглашение о совместной борьбе с Директорией и белогвардейцами. В соответствии с этим соглашением махновцы подчинялись оперативному командованию П. Дыбенко (командиру группы войск Екатеринославского направления, затем 1-й Заднепровской дивизии), сохраняя свою внутреннюю структуру и независимость, выборность, самодисциплину, самоназвание, черные флаги. В начале февраля 1919 года махновцы получили от командования украинских советских частей 9 тыс. винтовок, 20 пулеметов, батарею пушек, бронепоезд, а также немного амуниции и денег.

31 января 1919 года бронепоезд комдива Дыбенко прибыл на ст. Пологи, где в его честь махновцы устроили парад. В это время бронепоезд белых прорвал махновский фронт. На ликвидацию прорыва был направлен бронепоезд Дыбенко и гуляйпольцы, вооруженные только что привезенными комдивом несколькими тысячами винтовок. Победа над белыми, захват их бронепоезда и около сотни пленных, которые были привезены в Гуляйполе, вызвали общий подъем в «свободном районе». На переговорах с Дыбенко Махно заявил о том что, возможно, согласится руководить отрядами Красной армии, принять назначенных комиссаров и создать политотделы в полках.

В феврале 1919 года Махно во второй раз женился. Его женой стала Галина (Агафия) Андреевна Кузьменко 22 лет, которая родилась в семье писаря жандармской канцелярии. Галина закончила учительскую семинарию и с 1916 года работала в школе Гуляйполя. Она принимала участие во всех походах махновцев и оказывала большое влияние на решения Нестора. В армии она занималась как культурной, так и школьной работой.

В ноябре 1918 года в Курске состоялась учредительная конференция Конфедерации анархистских организаций Украины «Набат». На конференции было провозглашено: «Украинская анархистская революция станет первой в серии мировых анархистских революций». Началом такой революции анархисты считали повстанческое движение украинского крестьянства. В феврале 1919 года «набатовцы» сделали ставку на Махно и направились в Гуляйполе «для культурного труда». Группы «Набата» существовали в Александровске, Киеве, Одессе, Елизаветграде (ныне — Кировоград), Харькове, Екатеринославе и др. (всего в 35 городах).

14 февраля 1919 года между командованием Красной армии и махновцами было подписано официальное соглашение: махновские полки входили в 1-ю Заднепровскую дивизию как 3-я революционно-повстанческая бригада имени батьки Махно. Комбригом был утвержден Махно, а все выборные партизанские командиры остались на своих местах. В махновский штаб и полки были направлены политкомиссары. Таким образом, оперативное и административное подчинение частей Махно начдиву Дыбенко и командующему Антонову-Овсеенко предусматривало сохранение автономии внутренней организации бригады, выборного командования, добровольной мобилизации, самодисциплины, права бригады остаться в Приазовье и сохранение черных флагов. Все махновские части сливались в полки, которые получали военное снаряжение, продовольствие, фураж, деньги по штатному расписанию частей Красной армии. Перед махновцами была поставлена задача занять фронт против белых (расстояние составляло 180 км) и повести наступление на Ростов.