В конце декабря 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 км) и повести наступление на Ростов.

12—16 февраля в Гуляйполе состоялся II съезд повстанцев и крестьян 35 волостей (245 делегатов), который утвердил союз с Красной армией. В ходе съезда анархисты критиковали большевистскую диктатуру и установление власти никем не избранного Совнаркома Украины, охарактеризовав правительство большевиков как правительство «самозванцев-назначенцев». В своей речи Махно указал, что преследование анархистов в РСФСР, закрытие их газет, вооруженное подавления выступлений трудящихся – весь этот российский опыт не должен повториться в Украине. Позиция съезда была отражена в резолюции, где был высказан протест против большевистской «монополии на революции», против арестов и расстрелов представителей «революционных организаций». Съезд призывал строить свободное общество – безвластное и деполитизированное. Большое значение имело решение о создании Военно-революционного совета (ВРС) «свободного района» (государство в государстве). Махновский съезд утвердил раздел земли между крестьянами на принципах равенства, решил требовать от Центра автономии «свободного района».

В феврале 1919 года большевики начали массовые аресты левых эсеров и анархистов на юге Украины. Эти действия привели к тому, что Махно стал угрожать своей отставкой. Совет «свободного района» требовал прекращения «…партийной травли левых партий», недопущения в районе партийной диктатуры и ЧК, утверждения выборности в советских организациях, представительства в Александровском исполкоме.

В махновскую бригаду записалось до 24 тыс. человек, но только 7 тыс. были вооружены, остальных распустили по домам из-за нехватки оружия и амуниции. 10 марта началось наступление 1-й Заднепровской дивизии в Приазовье. На протяжении первой недели были одержаны существенные победы над Добровольческой армией, которая оставила Северную Таврию. Махновцы захватили Волноваху, Бердянск, подошли к Мариуполю. Корабли французской эскадры, которые стояли в мариупольском порту, обстреливали наступавших из 60 пушек. Около 5 тыс. белогвардейцев, зажатых в городе, предприняли ряд отчаянных контратак, однако все они окончились неудачей. 29 марта отряды Махно захватили город Мариуполь. Белые пытались удержать хотя бы порт, который они отчаянно защищали. После взятия Мариуполя 4 полка направились в Таганрог. Красный комдив предлагал наградить Махно орденом Красного Знамени. Командующий Украинским фронтом В. Антонов-Овсеенко называл тогда махновское движение «серьезным» и «героическим».

С марта 1919 года по селам началась продразверстка. Бесконтрольность, дикое самоуправство власти напоминали обычный грабеж. Массовое насилие продотрядов при отбирании хлеба в украинских селах привело к целому ряду крестьянских восстаний.

Командарм 2-й Украинской советской армии телеграфировал Антонову-Овсеенко: «Местные ЧК ведут усиленную кампанию против махновцев, в то время как махновцы воюют на фронте, в тылу их преследуют за принадлежность к махновскому движению… глупыми выходками мелкие «чрезвычайки» провоцируют махновское войско и население на бунт против Советской власти». Махновская контрразведка предупредила батьку о планировавшемся в ЧК покушении на него. Махно решил создать особый полк-«завесу», чтобы закрыть «свободный район» от проникновения комиссаров. Батько заявлял: «Комиссары не должны быть шпионами и контролерами на этой территории, следует прекратить агитацию против махновщины…»