Следствие по делу гуляйпольских анархистов тянулось около полутора лет. На следствии Нестор заявил, что не принадлежит к разбойничьей шайке, а является членом политической революционной организации, которая борется за свободу. В марте 1910 года состоялся военный суд, рассматривавший дело 13 гуляйпольских анархистов. Пятерых анархистов, одним из которых был Махно, приговорили к казни через повешение. 52 дня просидел Нестор в камере смертников. Это объясняется тем, что Махно заболел тифом. Тяжелая болезнь спасла смертника, который отказался подписать ходатайство о помиловании. Мать Нестора выяснила у военного прокурора, что смягчения приговора ее сыну можно добиться, доказав, что в момент совершения преступления Нестор был несовершеннолетним, и обратилась с просьбой о помиловании во все инстанции. Она настаивала на пересмотре дела в связи с несовершеннолетием Нестора (совершеннолетия тогда достигали в 21 год). В результате смертная казнь Махно была заменена пожизненной каторгой.
С августа 1911 года Нестор отбывал наказание в Московской центральной тюрьме (Бутырке). Все попытки сбежать оттуда, которые предпринимал Махно, завершились неудачей. Глубокая депрессия и ужасные условия карцера спровоцировали тяжелую болезнь — туберкулез, что вынудило тюремного врача удалить Нестору одно легкое… В тюрьме Нестор получил «университетское», как он сам впоследствии иронизировал, образование: как губка он впитывал в себя политические знания своих сокамерников. Близко сошелся Нестор с Петром Мариным (П. Аршинов), с которым впоследствии на протяжении 20 лет поддерживал дружеские отношения. Судьбы этих бунтарей с момента встречи тесно переплелись.
2 марта 1917 года, когда восставший народ уже полностью контролировал положение в Москве, политические заключенные вышли из московских тюрем с ореолом героев-мучеников: возле тюремных ворот их встречали веселые толпы людей с цветами и подарками. Среди освобожденных были и анархисты Махно и Аршинов. В конце марта Нестор приехал в родное село, где его восторженно встретили земляки как «заслуженного революционера». На волне революции власть в волостном центре перешла к выборному Комитету общественного спасения, в состав которого вошел Махно, ставший председателем Крестьянского союза Гуляйпольской волости. Затем Махно был избран председателем местных советов и возглавил почти все выборные организации села: земельный комитет, профсоюз металлистов и деревообработчиков, районную милицию, больничную кассу.
