В середине июля 1918 года Махно тайно посещает Гуляйполе, где образует инициативную группу по организации повстанческой борьбы и подготовке подвижных террористических групп для нападений на дома и подразделения гетманской охраны. В дальнейшем планировалось напасть на Гуляйполе, захватить село и напечатать там воззвание о начале восстания. Надо признать, что Махно сочетал в себе недюжинную храбрость и артистизм, это проявлялось в его поступках. Так, решив взорвать австрийский штаб в Гуляйполе, Махно с И. Лютым переоделись барышнями, спрятав под юбками бомбы. Но взорвать штаб так и не удалось, потому что в первый раз он был пустым, а на следующий день возле него оказались женщины и дети, и Махно отказался от плана, считая, что могут погибнуть невинные.

После нападения на филиал банка у Махно было 28 тыс. рублей. За 4 тыс. рублей он приобрел у крестьян пулемет, который установили на трофейном тарантасе, запряженном четверкой коней. Так в августе 1918 года в мире появился новый вид вооружения — тачанка. На тачанке подняли черный флаг, на котором были слова: «СТРАШНАЯ СМЕРТЬ БУРЖУЯМ — ВЕСЕЛАЯ ЖИЗНЬ БЕДНЯКАМ».

Уходя от преследования, Махно направился в Днепровские плавни. Оттуда он вел партизанскую борьбу и присоединил к своему отряду отряд гайдамаков. В столкновениях с махновцами было убито 8 офицеров и часовых, в плен попали 5 австрийцев. Махновцам достались 16 винтовок, пулемет, 15 коней. Пополнение отряда Махно зависело от наличия оружия, поэтому одной из главных задач махновцев был захват трофейного оружия.

В середине сентября сформировался махновский отряд, который уже мог выполнять боевые задания, — 120 сабель при 4 пулеметах. Этот отряд внезапно ворвался в Гуляйполе, но в селе оказалось много австрийских солдат. После короткого столкновения с австрийцами махновцам пришлось отступить.

После этого для подготовки «удара изнутри» в Гуляйполе было направлено несколько махновцев с телегами винтовок. 16 октября, воспользовавшись отсутствием основных австрийских сил, махновцы напали на Гуляйполе. В воскресенье, когда шла ярмарка, на ярмарочную площадь выехало несколько телег, в которых были спрятаны пулеметы и винтовки. Укрывшиеся в телегах неожиданно открыли огонь по группе австрийских солдат. Некоторые перепуганные австрийцы, подняв руки над головами, прокричали: «Ура, Махно!» В это же мгновение начал бить колокол гуляйпольской церкви. В центр села направились гуляйпольцы, которых заранее вооружил Махно. После короткой перестрелки отряд из 85 австрийцев капитулировал. Повстанцы захватили австрийскую бригадную кассу, часть денег Махно раздал пленным «для приобретения билета домой». По телеграфу Махно разослал телеграммы о победе гуляйпольского восстания, об установлении здесь Советской власти, призвав всех крестьян и рабочих Украины начать всеобщее восстание, последовав примеру Гуляйполя. Для руководства местной жизнью были избраны ревком и революционно-повстанческий штаб. Однако наступление превосходящих сил противника вынудило Махно после нескольких часов сопротивления оставить село. Выскользнув из окруженного Гуляйполя, Махно с сотней повстанцев вошел в с. Дибровка, в районе которого действовал повстанческий отряд под руководством матроса-анархиста Федора Щуся. Хотя отряды Махно (120 бойцов) и Щуся (53 бойца) объединились, Щусь некоторое время не признавал Махно командиром. Но последовавшие вскоре события подтвердили авторитет Нестора. Однажды ночью Дибровку окружил отряд, сформированный из австрийцев, гетманских часовых, местных помещиков и немецких колонистов. Выйдя незаметно из села, махновцы на рассвете, когда село заняли первые вражеские отряды, внезапно напали и отбили 4 пулемета и 20 лошадей, захватив 80 пленных. На следующий день к врагу присоединились новые подразделения войск с артиллерийской батареей, которая начала систематический артобстрел позиций повстанцев. Ситуация стала критической, повстанцы не могли сдержать натиск и начали разбегаться. Под командованием Махно и Щуся осталось лишь 30 бойцов, которые вместе с командирами отстреливались, отходя в глубь леса. Махно убедил товарищей, что не все еще потеряно и есть возможность выбраться из «огненного мешка». Неожиданно махновцы наскочили на гетманскую стражу. Прорвавшись сквозь цепь и не потеряв ни одного бойца, бойцы Махно с тыла ударили по захваченным врасплох часовым и вынудили их бежать. Через несколько часов Нестор собрал повстанцев, которые разбежались по степи, и взял Дибровку, где австрийский отряд охранял пленных. Это знаменательное событие произошло 28 октября 1918 года. Успех в этом бою утвердил авторитет Махно среди повстанцев, и впервые именно тогда, после этого боя, они назвали его батькой. С тех пор это прозвище стало неотделимо от Махно. Крестьяне увидели в нем своего защитника, он заслужил их уважение и преданность.

В конце октября махновцы курсировали вблизи Гуляйполя, нападая на станции Гайчур, Чаплино, Пологи, Гришино и Славгород, разбирая железнодорожные пути и пуская под откос эшелоны с австрийцами. 30 октября Махно снова ворвался в Гуляйполе, где продержался три дня. Деморализованные австро-венгерские солдаты отказались воевать с махновцами. Австрийское командование и гетманское правительство бросили против Махно части 12-го австро-венгерского корпуса и 8-го корпуса гетманских войск. Эти силы вытеснили махновцев из окрестностей Гуляйполя. При попытке захватить поезд с оружием на ст. Новогупаливцы махновский отряд был разгромлен. Под Нестором был убит конь. В ночь на 15 ноября произошло столкновение махновцев с австро-венгерскими частями возле с. Темировка. Часть махновского отряда разбежалась, остальные небольшими группами пытались держать оборону: 10 повстанцев во главе с Махно были окружены на окраине села. Батько с ручным пулеметом в руках бегал по узеньким улицам и отстреливался, пока его не ранили. Щусь тоже был ранен (в обе ноги) и не мог руководить боем. Из десяти повстанцев, которые остались с Махно, семь были убиты, а один, чтобы не сдаваться, застрелился. Махно, истекая кровью, также решил свести счеты с жизнью. Но друзья спасли его. Несмотря на яростный огонь, они пробрались к батьке и перетащили его в тачанку, посадив на скрещенные винтовки. В этом бою погибли и попали в плен более 200 махновцев… В 20-х числах ноября гетманская пропаганда распространила информацию о том, что «Махно убит, а банда его разгромлена».

Между тем в мире произошли важные события, которые в корне изменили положение и в Украине. В октябре 1918 года Германия и Австро-Венгрия потерпели военную катастрофу. Успешное наступление сил Антанты, экономический и политический кризис, революционные настроения и национальные движения разрушили Австро-Венгерскую империю, которая в конце октября 1918 года капитулировала. А 11 ноября 1918 года и Германия капитулировала перед Антантой. В тот же день было объявлено о постепенной эвакуации из Украины всех немецких и австро-венгерских войск. В середине ноября 1918 года Директория подняла всеукраинское народное восстание против гетманского режима. Эти события помогли махновскому отряду, оказавшемуся на краю гибели, продолжить борьбу.

27 ноября отряд Махно захватил Гуляйполе и окрестные села и на этот раз утвердился здесь надолго. Махно произвел реорганизацию своих военных формирований, пытаясь из мелких отрядов создать батальоны. Постепенно Гуляйполе стало центром всего революционного движения Екатеринославщины и Северной Таврии. Здесь были образованы органы управления подконтрольной повстанцам территории и руководство самим движением — революционный совет и штаб повстанцев. Махно был избран командующим всех повстанческих отрядов и начальником штаба, а его войско стало называться махновцами. К началу декабря отряд Махно уже состоял из 3 тыс. человек, вооруженных 30 пулеметами и 6 пушками.

14 декабря гетман Скоропадский отрекся от власти и выехал за границу. Началось возведение новой Украины — Украинской Народной Республики (УНР). Однако уже через несколько дней без объявления войны Советская Россия повела наступление на Украину. В. Антонов-Овсеенко, командующий красноармейскими силами, наступающий на Харьков, разослал директиву всем повстанческим отрядам Украины, требуя от них поддержать продвижение Красной армии.

13 декабря 1918 года махновская делегация подписала соглашение с петлюровцами, согласно которому махновцы должны были организовать фронт против белых. Махновцы получили от командования УНР вагон патронов и полвагона винтовок и взрывчатки. Ухудшение отношений между махновцами и силами Директории произошло после событий 20–21 декабря: в Екатеринославе петлюровцы разогнали городской совет и ревком большевиков. Губревком предъявил ультиматум с требованием освободить арестованных большевиков, угрожая при этом восстанием рабочих города. Большевики убедили Махно в «антинародности и буржуазности» Директории УНР. К батьке прибыл представитель губкома большевиков, чтобы направить махновские отряды на Екатеринослав. Он предложил Махно должность главнокомандующего советских революционных войск Екатеринославского района и обещал часть трофейного оружия, которое будет захвачено во время штурма Екатеринослава. ЦК КП(б)У разрешил местным парторганизациям входить в военный союз с Махно. У красных в Екатеринославе было около тысячи бойцов, Махно привел еще 700 человек. Он рассчитывал на внезапность нападения. Был определен главный участок прорыва — мост через Днепр. Железнодорожники пустили по мосту пустой поезд, а за ним поезд, в вагонах которого прятались махновцы. Этот поезд прибыл на екатеринославский вокзал и махновцы сумели захватить его. Начался ожесточенный бой в городе. К вечеру 28 декабря восставшие захватили большую часть города. Махновские отряды получили роскошные трофеи: 10 тыс. винтовок, 26 пулеметов, 4 пушки… Махновцы решили часть трофеев вывезти по железной дороге в Гуляйполе. Местный большевистский ревком пытался помешать этому. Махно, как командующий повстанческой армией, выступал за одинаковое представительство в Екатеринославском ревкоме от большевиков, левых эсеров и махновцев-анархистов и требовал объявить выборы в ревком, а после отказа выполнить эти требования решил не подчиняться решениям ревкома. 31 декабря 1918 года свежие силы войск УНР легко разгромили махновский отряд, который оборонял город. В Екатеринославе началась паника, большевистские отряды рабочих не подчинялись Махно. Многие махновцы при отступлении утонули в Днепре или погибли в уличных столкновениях.

5 января 1919 года, после того как в результате разгрома в Екатеринославе Махно вернулся в Гуляйполе, земляки высказали ему свое недовольство. Матери погибших обвинили командира в смерти своих сыновей. Махно объяснил поражение изменой большевиков и их отрядов. На вопрос, где остальные бойцы, батько сквозь зубы процедил: «В Днепре». Отношения между Махно и большевиками испортились. Большевики лишили его звания главнокомандующего повстанческой армией Екатеринославщины. Махно «проклинал большевиков и говорил, что нужно к черту поразгонять все большевистские штабы, тогда повстанцы будут с нами».