Захват Екатеринослава (ныне Днепропетровска) многому научил Нестора Махно. Он понял, что его крестьянское войско не годится для войны с любыми воинскими регулярными силами. Более того, на него стали совершать покушения, считая его за «диктатора».
В январе 1919 года махновцы (около 10 тысяч человек) столкнулись с Добровольческой армией. В боях с белыми и все теми же петлюровцами им пришлось туго, но на помощь пришли красные войска. Вскоре Н. И. Махно становится командиром 3-й бригады 1-й Заднепровской советской дивизии, которой командовал П. Е. Дыбенко. В донесениях писалось:
«На фронте советских войск Дыбенко ведет ожесточенные бои с казаками-чеченцами. Захвачено много пленных, оружия. Отличился в боях бывший вождь повстанческих отрядов, теперь командир бригады – Махно».
Нестора Ивановича хвалили, как известного революционера, на страницах газет «Правда» и «Известия». В Гражданской войне его стали знать не только на Екатеринославщине.
Бригада Махно провела ряд успешных столкновений с белыми войсками. В марте 1919 года махновцы заняли город Бердянск и узловую железнодорожную станцию Волноваха. Затем захватили Мелитополь, но приблизиться к Таганрогу белые им не позволили. Бригада действовала в составе 2-й Украинской советской армии, которой командовал А. Е. Скачко. Известно, что после взятия Мелитополя был поднят вопрс о награждении отличившихся командиров, в том числе Н. И. Махно, орденом Красного Знамени, но положительно решен он не был.
На занятой советскими войсками территории вводилась продразверстка. В ее условиях крестьяне не могли распоряжаться продуктами своего труда: хлеб изымался, по сути дела, без компенсации. Да и к тому же конфискация помещичьих земель часто проходила без раздела ее между крестьянами, а для организации совхозов. Продразвестка стала причиной многих крестьянских восстаний и в ходе Гражданской войны, и после ее окончания, что влекло применение военной силы и жестокого террора власти по отношению к повстанцам.
Махно знал крестьянскую жизнь и стремления тех, кто трудился на земле. Когда в феврале 1919 года в Гуляй-Поле состоялся II съезд махновцев, то там уже звучали антисоветские выступления его делегатов. На III таком съезде Нестор Махно заявил, что советская власть изменила «октябрьским принципам». Свое слово сказали и анархисты-«набатовцы».
Повстаческая армия Махно в своей массе состояла из беспартийных крестьян, а не из деклассированных элементов, как порой пишется. На первых порах в ней существовали партийные ячейки не только анархистов, но и левых эсеров с большевиками. Младшие командиры в армии были выборные, старших назначал сам «батько».
Отношения Махно с советской властью на первых порах сложностью не отличались. Весной 1919 года он отправил в Москву и Петроград 90 вагонов с хлебом (зерном). Но с другой стороны, махновцы грабили эшелоны с продовольствием, которые шли в Донбасс: это «списывалось на атаманов». Экспроприация чужой собственности у махновцев была поставлена на широкую ногу.
В апреле 1919 года в 3-й бригаде по приказу ее командира были арестованы все политкомиссары (их потом отпустили). В Гуляй-Поле спешно прибыл командующий Красной армией Украины В. А. Антонов-Овсеенко. С места он отправил правительству в Киев телеграмму следующего содержания:
«Пробыл у Махно весь день. Махно, его бригада и весь район – большая боевая сила. Никакого заговора нет. Сам Махно не допустил бы. Район вполне можно организовать, прекрасный материал, но нужно оставить за нами, а не Южфронтом. При надлежащей работе станет нескрушимой крепостью. Карательные меры – безумие. Надо немедленно прекратить газетную травлю махновцев».
Когда вспыхнул мятеж Григорьева, Махно не поддержал его, но и не осудил за антисоветское выступление. В Киеве сильно опасались за их возможное союзничество. За Махно заступился начдив Павел Дыбенко, назвавший кобрига «честным революционером», «борцом за права угнетенного народа».
В Киеве был поднят вопрос о замене командира 3-й бригады 1-й Заднестровской дивизии. Когда об этом стало известно Н. И. Махно, он сделал ответный ход: собрание командиров махновских отрядов в городе Мариуполе заявило о создании отдельной Повстанческой армии во главе, разумеется, с «батькой» Махно.
Когда советские 8-я и 13-я армии начали наступление на Донецкий каменноугольный бассейн, в их рядах находилась бригада махновцев (около 7 тысяч человек), занявшая станцию Кутейниково, оказавшись у белых фактически в тылу.
Деникин сделал ответный ход: он перебросил в стык между бригадой Махно и 9-й дивизией 13-й армии 3-й Кубанский конный корпус генерала А. Г. Шкуро. Белоказаки, поддержанные бронепоездами, в первый же день прорвали советский фронт у железнодорожной станции Ларино (Донбасс). Махновская бригада откатилась назад на сто километров (самовольно оставила занимаемые позиции), а в линии фронта образовалась брешь в 30 километров. Фланг и тыл 13-й армии оказались открытыми для удара противника. Приазовье отдавалось в руки деникинцам.