Тогда же немцы и гайдамаки заняли Гуляйполе. Нестору Ивановичу удалось скрыться, но гетманцы расстреляли его брата Емельяна и сожгли дом братьев Махно. Не имея пока сил для борьбы, Махно отправился устанавливать связи с анархистскими организациями: побывал в Ростове-на-Дону, Таганроге, Астрахани, Саратове, Царицыне, а в июне добрался до Москвы. Здесь он нашел своего «бутырского наставника» Аршинова, который свел его с другими видными анархистами: Кропоткиным, Черным, Боровым и Гроссманом. Однако все эти встречи убедили Махно только в одном: вожди анархизма не спешат в крестьянские массы, а предпочитают отсиживаться в столице. «Фактически не было людей, — писал он позже, — которые взялись бы за дело нашего движения и понесли бы его тяжесть до конца». Были в это время и другие встречи:
Махно приняли председатель ВЦИК Свердлов и председатель Совнаркома Ленин. Большевистские лидеры отнеслись к нему очень благожелательно и обещали помочь в организации партизанской борьбы против немцев.
В июле Махно скрытно вернулся в Гуляйполе. К этому времени озлобление крестьян против Скоропадского и его германских союзников успело достичь необходимого градуса. Едва прошел слух о возвращении Махно, как к нему со всех сторон стали собираться добровольцы. Началась партизанская война. В первых операциях Махно не было ничего героического, скорее они напоминали его прошлые бандитские налеты образца 1906 г.: повстанцы нападали на помещичьи имения, разоружали небольшие гарнизоны, ограбили банк в местечке Жеребец. Но постепенно предприятия их делались все более дерзкими. В этой войне вырос и окреп талант Махно как военного руководителя. Он был смел, расчетлив, постоянно изобретал разные хитрости. Любовь и уважение к нему крестьянства росли с каждым днем, повстанцы стекались со всей округи, и силы Махно росли. В октябре он отбил у гетмаицев Гуляйполе, которое стало с этих пор его ставкой. К этому времени под его началом было более 20 тысяч повстанцев.
После ноябрьской революции 1918 г. в Германии немцы стали быстро покидать Украину. Вместе с ними уехал гетман Скоропадский. О своих претензиях на власть заявила Директория, во главе с «головным атаманом» Симоном Петлюрой. Отношения с ним у Махно были не лучше, чем с прежней властью. Уже в декабре между махновцами, которые контролировали к этому времени весь Александровский уезд, и петлюровцами начались военные столкновения. Из ненависти к Директории Махно пошел даже на союз с большевистским подпольем в Екатеринославе. 27 декабря в городе вспыхнуло восстание. Махновцы с ходу овладели вокзалом и железнодорожным мостом. Завязался ожесточенный уличный бой. Через два дня город был взят. Повстанцы бросились его грабить. Но 31 декабря, собравшись с силами, петлюровцы перешли в контрнаступление и выбили их из Екатеринослава. Понеся огромные потери, Махно вернулся в Гуляйполе.
В конце января 1919 г. к Екатеринославу подступили части Красной Армии во главе с Дыбенко. Махно заключил с ним союз и договорился о совме' стных действиях. (Это было необходимо, так как надвигался враг более грозный, чем петлюровцы, — Добровольческая армия Деникина.) Повстанческие отряды Махно вошли при этом в состав Красной Армии, но сохранили полную внутреннюю автономию. (Позже они составили 3-ю бригаду в составе 1-й Заднепровской дивизии Дыбенко.) Уже через несколько дней махновцы вступили в затяжные бои с белогвардейцами. Гуляйподе несколько раз переходило из рук в руки. Получив от Дыбенко бронепоезд, Махно не только удержал родное село, но и выбил деникинцев из Александровска. В марте, развивая наступление, он после тяжелого боя взял Мариуполь. За эту операцию его наградили орденом Красного Знамени. В мае он участвовал в наступлении на Донбасс, взял станцию Кутейниково и вышел в тыл белым.