Родился будущий авторитетный матрос-анархист в Москве в 1895 году в мещанской семье. Отец отставной солдат, ветеран русско-турецкой войны. Обучался в Пресненском начальном городском и церковно-приходском училищах. В детстве был очевидцем баррикадных боев на Пресне в декабре 1905 года. Именно тогда он увидел, что после того, как боевики эсеровских и большевистских дружин оставили последние баррикады, там до конца держались лишь рабочие-анархисты. Затем пятнадцатилетнего Анатолия как сына солдата, прослужившего в армии три срока, устроили на казенный счет на обучение в Лефортовское военно-фельдшерское училище. На третий год учебы он демонстративно отказался участвовать в торжественном молебне по случаю «тезоименитства» императрицы, за что был исключен. После этого решил стать моряком, но последовательно провалил вступительные экзамены в Кронштадтскую и затем Ростовскую (на Дону) морские школы. Работал на Богородско-Глуховской текстильной мануфактуре в Богородске (ныне Ногинск) аптекарским учеником. Но был уволен за попытку закурить на территории фабрики. С мая 1914 года плавал на Черном море кочегаром торгового парохода «Тайфун». В начале Первой мировой войны предпринимает безуспешную попытку поступить в Ростовское мореходное училище. В апреле 1915 года, во время стоянки «Тайфуна» в Одессе, команда объявила забастовку. Судовладельцы обратились в портовую жандармерию. В итоге все годные к службе в армии были сняты с судна и направлены на фронт. Поскольку А. Г. Железняков еще не достиг призывного возраста, его просто уволили.
А. Г. Железняков вернулся в Москву и поступил слесарем в сборочный цех завода Густава Листа в Бутырках, где изготавливались артснаряды и судовые насосы. Там Железняков проработал до осени 1915 года, попал в поле зрения Московского охранного отделения. В октябре 1915 года он был призван на военную службу, зачислен на Балтийский флот. Проходил обучение в Петергофе в Машинной школе. Затем получил назначение во 2-й Балтийский флотский экипаж, а оттуда на учебное судно «Океан». Летом 1916 года в результате конфликта с командованием судна дезертировал. Бежал в Москву, оттуда в Саратов, где по поддельным документам недолго поработал грузчиком в порту, после чего направился в Одессу, где поступил кочегаром на пароход «Принцесса Христина». Мечтал бежать в Америку, но в октябре 1916 года за организацию беспорядков на судне был уволен. С ноября 1916 до февраля 1917 года А. Г. Железняков работал кочегаром на нескольких судах на Черном море. Февральская революция застала его в Батуми. После мартовской амнистии дезертирам царского времени, будучи уже убежденным анархистом, А. Г. Железняков появился в Кронштадте и сразу направился в местный Совет.
Депутату Кронштадтского Совета матросу Пожарову он объявил, что был вынужден из-за преследования самодержавия оставить военную службу и перейти на нелегальное положение. А сейчас вернулся, чтобы послужить делу революции, и попросил Пожарова передать всем членам Центробалта, что матрос Железняков снова в боевом строю и не пожалеет своей жизни для борьбы с контрой. После этого он был представлен председателю Кронштадтского комитета партии большевиков С. Рошалю.
Встретившись с Железняковым и оценив его готовность служить революции, С. Рошаль распорядился зачислить его матросом на минный заградитель «Нарова». А уже через несколько дней его как «старого революционера» избрали в числе 38 делегатов кронштадтцев на 1-й съезд представителей Балтийского флота.
Появляясь на трибунах, Железняков всегда произносил зажигательные речи, которые воспринимались матросами с полным восторгом. Оратором он был превосходным. Богатая биография, неплохой уровень образования, решительность и обаяние, умение убеждать быстро выводят А. Г. Железнякова в лидеры матросских анархистов. Ряд исследователей считают, что анархизм являлся скорее не следствием идейных убеждений Железнякова, а был доминирующей чертой его характера.
В середине мая А. Г. Железняков во главе отряда матросов-анархистов занял дачу бывшего царского тайного советника Д. Н. Дурново, которая стала штаб-квартирой партии анархистов в России. С этого момента А. Г. Железняков стал заметной фигурой и в анархистской среде.
В период июньского кризиса А. Г. Железняков во главе отряда из 50 матросов снова прибыл в Петроград для вооруженной защиты дачи Дурново. Одновременно с этим он руководил анархическими демонстрациями в столице, участвовал в разгроме тюрьмы «Кресты» и освобождении группы политзаключенных, среди которых было много анархистов. Все это значительно повысило его популярность как среди матросов, так и среди анархистов. Когда 16 июня верные Временному правительству войска начали операцию по очистке дачи Дурново от анархистов и криминала, Железняков лично метал в казаков бомбы. При этом сам получил тяжелое ранение, был арестован и заключен в «Кресты». Военный суд приговорил закоренелого анархиста к 14 годам каторги. Сидя в «Крестах», Железняков писал возвышенные стихи: