Программа Махно предусматривала: «социализацию» (обобществление) земли, фабрик и заводов; отмену продразверстки; свободу слова, печати и собраний, но только всем «левым партиям и группам»; неприкосновенность личности; отказ от диктатуры коммунистической партии; свободу выборов в Советы трудящихся крестьян и рабочих. С 15 апреля 1919 года бригада Махно входила в состав 7-й Украинской советской дивизии. После начала восстания бывшего советского начдива Ничипора Григорьева 7 мая 1919 года Махно сначала занял выжидательную позицию, затем решил остаться на стороне большевиков. Но одновременно он на собрании командиров повстанческих отрядов в Мариуполе поддержал идею создания отдельной повстанческой армии.
В начале июня 1919 года бригада Махно, не получая от командования Красной Армии боеприпасов и снаряжения, в боях с частями Кавказской дивизии Андрея Шкуро понесла большие потери и вынуждена была отступить. 6 июня 1919 года за самовольное оставление фронта Махно был объявлен вне закона. Ему инкриминировали «развал фронта и неподчинение командованию». 8 июня командиром бригады на место Махно был назначен большевик прапорщик Александр Круссер, но уже в ночь с 9 на 10 июня он был убит то ли махновцами, то ли белыми. 9 июня 1919 года Махно разорвал соглашение с Советским правительством и направил телеграмму Ленину, Каменеву, Зиновьеву, Троцкому, Ворошилову и Раковскому, в которой сообщил о своей преданности революционному делу и объяснил принятие решения о разрыве с Красной Армией постоянными нападками на него со стороны «представителей центральной власти» и «прессы коммунистов-большевиков». Одновременно в телеграмме Махно просил освободить его от командования дивизией (в начале июня был издан приказ о переформировании повстанческой бригады махновцев в стрелковую дивизию) «ввиду создавшегося невыносимо-нелепого положения». C остатками бригады Махно отступил в Херсонскую губернию. Здесь он совместно с Григорьевым продолжил вооруженное сопротивление как войскам Деникина, так и Красной Армии, одновременно принимая мелкие отряды повстанцев и красноармейцев-окруженцев и формируя боеспособные части повстанческой армии. В середине июля 1919 года Махно возглавил Реввоенсовет объединенной Революционно-повстанческой армии Украины (РПАУ). А вскоре после этого Махно лично застрелил другого знаменитого атамана, Никифора Александровича Григорьева, обвинив его в сговоре с Деникиным и еврейских погромах. Двум медведям было слишком тесно в одной берлоге Революционно-повстанческой армии. Два белых офицера, посланных от Деникина с письмом к Григорьеву, были перехвачены махновцами и повешены. На допросе в ОГПУ адъютант Махно Алексей Чубенко вспоминал: «При входе Григорьева его первыми словами были: «А у вас тут жидов нет?» Кто-то ему ответил, что есть. Он заявил: «Так будем бить!» В это время подошел Махно и спросил: «Это ваш универсал?» Григорьев ответил: «Да, мой!» Махно ничего не сказал, а только покачал головой и сказал, что он немного с ним не согласен. Григорьев ничего не ответил. Махно велел созвать членов штаба. На повестке было соглашение махновцев с Григорьевым. Разговоры продолжались целые сутки… Григорьев в какой-то момент заявил, что если он говорил «будем бить коммунистов и петлюровцев», то потому, что он уже видел, кто они такие, а Деникина еще не видел, а потому бить его не собирается.
Когда сказал это Григорьев, то мы вышли совещаться. За то, чтобы соединиться с Григорьевым, было 4 голоса, а за то, чтобы Григорьева тут же расстрелять или же не соединяться – 7 голосов. Махно стал говорить, что во что бы то ни стало нужно соединиться и что расстрелять Григорьева мы всегда успеем. Нужно забрать его людей: те – невинные жертвы, так что во что бы то ни стало нужно соединиться. После такой речи Махно было за соединение 9 голосов и два воздержавшихся…»
И демонизировать махновское войско не стоит. И грабежи, и пьянство, и бессудные казни были ему присущи в такой же мере, как и другим повстанческим армиям. Да и белые и красные в этом отношении от махновцев недалеко ушли. Сам Махно неоднократно издавал приказы по борьбе с пьянством, грабежами и бессудными убийствами и порой лично расстреливал мародеров. Но помогало это мало.
27 июля 1919 года в селе Сентове, близ Александрии, Херсонской губернии, по инициативе Махно был созван съезд повстанцев Екатеринославщины, Херсонщины и Таврии, на котором должно было состояться формальное объединение армий Махно и Григорьева. Первым на съезде выступил Григорьев, призвавший отдать все силы на изгнание большевиков из Украины, не пренебрегая в борьбе с ними никакими союзниками. Затем выступили Чубенко и Махно, указавшие, что борьба с большевиками может быть только революционной, и союз с белыми генералами повстанцам ни к чему, поскольку они – злейшие враги народа. Если Григорьев призывает к такому союзу, то он – враг народа.