Махно решил сделать из Херсона новый базовый район своего движения, но здесь уже был свой харизматичный атаман — Григорьев, и батьке пришлось пойти с ним на компромисс. Махно с отрядом в тысячу сабель направился в село Верблюжки искать встречи с атаманом. Но в то время штаб атамана находился в с. Компанеевка. Отряды Григорьева в июне 1919 года насчитывали 3 тыс. повстанцев. Тогда атаману еще удавалось проводить громкие рейды, результатами которых были захват на несколько суток узловых станций Христиновка, Бобринская, Знаменка.
Махно получил информацию о том, что в Елизаветграде чекисты арестовали анархистов и махновцев. 10 июля 500 махновцев напали на Елизаветград, но так и не сумели взять центр города и тюрьму с ходу: красные пришли в себя и ударили по флангам наступающих. Махновцы отступили, разгромив местный вокзал и разогнав милицию. Следующее нападение махновцев, 12 июля, было удачнее: тюрьма была взята, и все политзаключенные выпущены на свободу. Однако закрепиться в городе и на этот раз махновцы не смогли. 13 июля они вышли к Компанеевке, вокруг которой действовали отряды григорьевцев. Махно встретил Григорьева с его «Универсалом» в руках и заявил, что хотя не полностью согласен с «Универсалом», но готов к совместным действиям и союзу. Объединение сил предусматривало, что Махно становился председателем Повстанческого совета единой армии, Григорьев — командующим объединенным войском, а брат Махно Григорий — начальником общего штаба. Григорьев пообещал не допускать еврейских погромов и заявил, что совершенные в прошлом погромы проходили без его ведома. На совещании махновских командиров большинство высказалось против этого союза, предложив расстрелять Григорьева за еврейские погромы. На что Махно ответил, что расстрелять Григорьева «всегда можно успеть», необходимо присоединить его повстанцев к себе. Было решено, что Григорьев займется обороной района от наступления белых. Союз между батьком и атаманом длился около двух недель, на протяжении которых объединенные силы совершили нападения на ст. Знаменка, Александрия, Помошная, сводя на нет попытки Красной армии окружить и уничтожить повстанцев.
Между тем Махно готовил переворот. Он считал, что Григорьев воевать против белых не будет, и к нему уже начали поступать жалобы на атамана от крестьян, местечковых евреев, да и от некоторых махновцев. Махновцы перехватили белогвардейских курьеров-офицеров с письмом для Григорьева, в котором речь шла о возможности союза между атаманом и белыми. Махно созвал совещание своего штаба и командиров, на котором единогласно было решено немедленно уничтожить атамана. 27 июля по инициативе Махно в селе Сентово был созван съезд повстанцев и крестьян Херсона для выработки программы защиты «свободного района» от красных и белых. Первым с речью на съезде выступил атаман, который заявил, что главным врагом крестьян являются большевики и в борьбе с ними крестьяне не должны гнушаться союзом с Деникиным. Далее выступил А. Чубенко, который обвинил Григорьева в сговоре с белыми генералами, в грабежах кооперативов, в организации еврейских погромов, назвал атамана «врагом крестьянства» и «царским слугой».
Возмущенный Григорьев требовал доказательств и прекращения обвинений. Для выяснения дела Махно предложил атаману зайти в помещение штаба. В штабе завязалась драка, во время которой Чубенко ранил атамана в плечо. Однако Григорьев, несмотря на ранение, успел выскочить во двор и позвать на помощь. Но во дворе его обступили Махно, Чубенко и Каретник и разрядили в него свои револьверы. Неожиданно раздались пулеметные очереди над головами тех, кто собрался на площади.
Перепуганная толпа участников съезда разбежалась, а махновцы разоружили несколько сотен григорьевцев, которые оказали сопротивление. На следующий день съезд повстанцев возобновил свою работу, он одобрил уничтожение Григорьева. Также было принято решение о вступлении его отрядов в махновское войско. Правительство УССР в июле 1919 года предложило махновцам амнистию при условии их возвращения в Красную армию. Однако махновцы, зная цену обещаниям большевиков, не спешили переходить под тяжелую руку Троцкого.
К концу июля махновские отряды контролировали северную часть Херсона. По селам махновские агитаторы обустраивали «свободные советы» и формировали повстанческие отряды. Район, занятый махновцами, был довольно важным в стратегическом отношении: здесь пересекались главные железные дороги, которые связывали все части Украины. Однако это же ставило махновцев в опасное положение — по ним наносили систематические удары силы Красной армии, которая стремилась выбить их с железнодорожных станций. Одновременно белогвардейцы, стремясь прорваться в тылы красных и отрезать Причерноморье, вступали в ожесточенные бои с махновскими отрядами.
5 августа 1919 года для борьбы с красными и белыми Махно провозгласил создание Повстанческой армии, которая вступила бы в борьбу против «буржуазии и ее охранников, советских комиссаров, членов карательных отрядов ЧК». Каждый повстанец обязывался задерживать и при малейшем сопротивлении расстреливать на месте этих представителей «диктатуры пролетариата». По оценкам военных специалистов УНР, на начало августа 1919 года махновское движение охватило более 50 тыс. человек, включая беженцев. Однако вооруженных и готовых воевать повстанцев было не слишком много — до 5 тыс. пехоты и до 1,5 тыс. кавалерии при 35 пушках без боеприпасов.
С 29 июля по 13 августа между красными и махновцами разгорелись бои за узловые железнодорожные станции Херсона. На ст. Помошная махновцы разгромили соединение 45-й дивизии. Но части 58-й дивизии все же захватили Помошную и окружили главные силы махновцев. Впрочем, это был лишь временный успех красных. Прорвавшись в с. Песчаный Брод, махновцы принялись громить красные тылы и советские учреждения. 10 августа станции Помошная, Новоукраинка, Компанеевка заняла карательная группа Затонского, прибывшая на нескольких бронепоездах из Киева. Во время ожесточенных боев за Помошную Затонский во главе карательного отряда захватил с. Песчаный Брод. Он решил наказать местных крестьян, пускавших под откос или останавливавших поезда и захватывавших имущество, которое большевики вывозили с юга Украины. По приказу Затонского было расстреляно несколько диверсантов, в том числе и тесть Махно. За три недели до своей гибели старый Кузьменко устроил свадьбу своей дочки Галины со славным повстанцем по церковному обряду. Махно и многие его командиры приехали в село, где были накрыты огромные столы. Село еще не видело такой роскошной свадьбы — она бурлила три дня. Карательная акция Затонского в Песчаном Броде сильно повлияла на настроение Махно и его командиров, которые до этого все еще думали о возможном союзе с Красной армией. Конный полк Щуся уничтожил карательный отряд, из которого спаслись лишь Затонский и 15 бойцов, которым удалось бежать. Тогда же махновцы расстреляли 16 пленных красноармейцев.
Частям 45-й, 47-й, 58-й советских дивизий было приказано объединиться в Южную группу и готовиться к отступлению на север Украины. Паника, хаос, дезертирство, отчаяние охватили рабочих и красноармейцев. В то время как большевики отходили на север, стремясь вывезти как можно больше ценностей, махновцы формировали свою Повстанческую армию как единственную защитницу народа от белогвардейцев. Махно заявил, что его армия продолжит борьбу на юге, даже если она и приобретет «партизанские формы». Махновские агитаторы, используя сложившуюся ситуацию, призывали «всех, кому дороги завоевания революции на Украине», не отступать, выполняя преступные приказы Троцкого, а, вступив в Повстанческую армию, преградить путь белым.
15—19 августа в частях 58-й дивизии произошли события, в некоторой степени определившие далынейшую судьбу Повстанческой армии. В эти дни на сторону Махно перешло около 20 тыс. красноармейцев.
Белогвардейцы замкнули окружение красных, захватив Елизаветград и подойдя к Киеву с Левобережья. Командование Южной группы выставило перед Махно требование — пропустить эшелоны группы через контролируемый махновцами район. Махно предложил красным два варианта выхода из ситуации: разоружиться, передав все оружие махновцам, или же войти в состав Повстанческой армии махновцев. Махно телеграфировал в Киев, требуя своего назначения на должность командующего всеми советскими войсками, которые еще остались на юге Украины, — Красной армией юга Украины. Однако большевистские лидеры отклонили предложение Махно.
На протяжении первого месяца своего существования Повстанческая армия Украины, пополнившись красноармейцами, восставшими крестьянами Херсона, григорьевцами, превратилась в реальную военно-политическую силу — она насчитывала 30 тыс. бойцов. Махно разделил свою армию на 4 бригады, 3 конных и 3 артиллерийских дивизиона. 1 сентября 1919 года в с. Добровеличковка состоялся съезд представителей повстанцев, который подвел итоги деятельности по созданию Повстанческой армии. Был избран Военно-революционный совет во главе с Лащенко, командующим Повстанческой армией вновь был избран Нестор Махно, начальником штаба — Белаш. Армия получила официальное название — Революционно-повстанческая армия Украины имени батьки Махно. Полустихийное возникновение Повстанческой армии на базе нескольких крестьянских отрядов стало событием, которое подтверждало расчеты анархистов на самоорганизацию и самодеятельность общественных сил.
