В этот период в Гуляй Поле собралось большое количество анархистов, в частности члены созданной в конце 1918 года Украинской анархистской организации «Набат». У Махно стала выходить газета «Путь к свободе».

У Нестора Ивановича начались конфликты с большевиками. Несмотря на это, Махно, не поддержал антисоветский мятеж атамана Н. Григорьева — комдива Красной Армии, взявшего перед этим Херсон, Николаев, Одессу. К концу мая Красная Армия подавила восстание, но сам Н. Григорьев ушел.

19 мая конница белого генерала А. Шкуро прорвала фронт на стыке между дивизией Н. И. Махно; которой стала его бригада и 13-й дивизией Красной Армии. Несмотря на то, что красные, опасаясь самостоятельности и непредсказуемости «батьки», снабдили его бойцов итальянскими винтовками, к которым не подходили отечественные патроны, махновцы в течение двух недель дрались с белогвардейцами, отказавшись перейти на их сторону. Прибывший на фронт Лев Троцкий, не принявший всерьез наступление белых, продолжил начатую Х. Раковским травлю махновцев и приказал арестовать Махно, отказавшегося от должности комдива. Все его командиры заявили, что никому другому они подчиняться не будут. Дивизия перестала существовать, а сам Южный фронт под ударами деникинцев развалился, благодаря недалекой политике большевиков.

Несмотря на то, что войска Деникина рвались к Москве, Л. Троцкий и его «соратники» пытались «ликвидировать махновщину в кратчайший срок». Нестор Иванович с отборными частями ушел к Херсону, где встретился с Н. Григорьевым. Красные не придумали ничего лучшего, как расправиться с оставшимися махновцами — 12 июня 1919 года в бронепоезде К. Ворошилова был арестован начштаба Махно Я. Озеров с группой и все без суда расстреляны. В ответ московские анархисты — радикалы взорвали большевиков во главе с В. Загорским в Леонтьевском переулке. Большевики возненавидели Махно, но он уже был им не по зубам.

27 июля 1919 года недалеко от Херсона махновцы убили атамана Григорьева, а его части перешли к Махно. Газета «правда» ответила на это статьей — «Махновщина и Григорьевщина», в которой написала, что Н. Махно навсегда оставил «арену политической борьбы».

17 августа и позже оставшиеся в Красной Армии махновцы Калашников, Дерменжи, Буданов, «железный полк» Полонского перешли к Нестору Ивановичу. Деникинцы наступали, и Махно повернул свою пятнадцатитысячную армию на них. Нестор Иванович говорил тогда: «Главный наш враг, товарищи крестьяне — Деникин» Коммунисты — все-таки революционеры. С ними мы сумеем посчитаться потом».

1 сентября 1919 года в селе Добровеличковке на Херсонщине была создана Революционная Повстанческая Армия Украины, состоявшая из 4-х корпусов, под командованием Нестора Махно. Через три недели в Жмеринке был заключен договор С. Петлюры и Н. Махно о совместной борьбе с белыми. В конце сентября под Уманью махновцы прорвали деникинский фронт и прошли к ним в тыл. В течение октября армия Н. Махно, численность которой достигла 100 000 штыков, взяла Александровск, Бердянск, Никополь, Мариуполь, Синельников, Лозовую. Взяли Екатеринослав и Гуляй Поле. Армия Деникина, выходившая на Москву, вынуждена была направить против махновцев свои лучшие части — генералов Слащева и Шкуро — тылы, склады, снабжавшие армию, связь — все было парализовано. Своими действиями Н. И. Махно изменил ход гражданской войны — деникинцы, воюя с ним, не дошли до Москвы.

Л. Троцкий в ответ на действия махновцев бросил на них группу И. Якира, требуя «искоренить партизанщину». Красные даже заняли Гуляй Поле. Благодаря этому белые смогли переформироваться и уйти в Крым, загородившись Перекопом. Нестор Иванович заболел тифом, красные усилили карательные акции.