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

А. Г. Железняков вернулся в Москву и поступил слесарем в сборочный цех завода Густава Листа в Бутырках, где изготавливались артснаряды и судовые насосы. Там Железняков проработал до осени 1915 года, попал в поле зрения Московского охранного отделения. В октябре 1915 года он был призван на военную службу, зачислен на Балтийский флот. Проходил обучение в Петергофе в Машинной школе. Затем получил назначение во 2-й Балтийский флотский экипаж, а оттуда на учебное судно «Океан». Летом 1916 года в результате конфликта с командованием судна дезертировал. Бежал в Москву, оттуда в Саратов, где по поддельным документам недолго поработал грузчиком в порту, после чего направился в Одессу, где поступил кочегаром на пароход «Принцесса Христина». Мечтал бежать в Америку, но в октябре 1916 года за организацию беспорядков на судне был уволен. С ноября 1916 до февраля 1917 года А. Г. Железняков работал кочегаром на нескольких судах на Черном море. Февральская революция застала его в Батуми. После мартовской амнистии дезертирам царского времени, будучи уже убежденным анархистом, А. Г. Железняков появился в Кронштадте и сразу направился в местный Совет.

Депутату Кронштадтского Совета матросу Пожарову он объявил, что был вынужден из-за преследования самодержавия оставить военную службу и перейти на нелегальное положение. А сейчас вернулся, чтобы послужить делу революции, и попросил Пожарова передать всем членам Центробалта, что матрос Железняков снова в боевом строю и не пожалеет своей жизни для борьбы с контрой. После этого он был представлен председателю Кронштадтского комитета партии большевиков С. Рошалю.

Встретившись с Железняковым и оценив его готовность служить революции, С. Рошаль распорядился зачислить его матросом на минный заградитель «Нарова». А уже через несколько дней его как «старого революционера» избрали в числе 38 делегатов кронштадтцев на 1-й съезд представителей Балтийского флота.

Появляясь на трибунах, Железняков всегда произносил зажигательные речи, которые воспринимались матросами с полным восторгом. Оратором он был превосходным. Богатая биография, неплохой уровень образования, решительность и обаяние, умение убеждать быстро выводят А. Г. Железнякова в лидеры матросских анархистов. Ряд исследователей считают, что анархизм являлся скорее не следствием идейных убеждений Железнякова, а был доминирующей чертой его характера.

В середине мая А. Г. Железняков во главе отряда матросов-анархистов занял дачу бывшего царского тайного советника Д. Н. Дурново, которая стала штаб-квартирой партии анархистов в России. С этого момента А. Г. Железняков стал заметной фигурой и в анархистской среде.

В период июньского кризиса А. Г. Железняков во главе отряда из 50 матросов снова прибыл в Петроград для вооруженной защиты дачи Дурново. Одновременно с этим он руководил анархическими демонстрациями в столице, участвовал в разгроме тюрьмы «Кресты» и освобождении группы политзаключенных, среди которых было много анархистов. Все это значительно повысило его популярность как среди матросов, так и среди анархистов. Когда 16 июня верные Временному правительству войска начали операцию по очистке дачи Дурново от анархистов и криминала, Железняков лично метал в казаков бомбы. При этом сам получил тяжелое ранение, был арестован и заключен в «Кресты». Военный суд приговорил закоренелого анархиста к 14 годам каторги. Сидя в «Крестах», Железняков писал возвышенные стихи:

Однако поэзией Железняков занимался недолго. В начале сентября 1917 года его возлюбленная юная анархистка Люба (Л. А. Альтшуль), добившись свидания, передала Железнякову стальные пилки и браунинг. Распилив ночью 6 сентября решетку и отогнув ее прутья, Железняков спрыгнул из камеры на крышу соседнего корпуса. Оттуда он перебрался на крышу другого корпуса, стоящего близко от дороги, где его уже ждал автомобиль…

После этого А. Г. Железняков пробирался в Гельсингфорс, где снова занялся анархистской пропагандой среди матросов.

Вскоре А. Г. Железнякова привлекли к работе в Центробалте по созыву 2-го съезда моряков Балтийского флота.

25 сентября Железняков стал секретарем открывшегося в Гельсингфорсе 2-го съезда представителей Балтийского флота. Вместе с председателем съезда, которым был избран только что освобожденный из «Крестов» под залог большевик Павел Дыбенко, он заседал на бывшей царской яхте «Полярная Звезда», где работал Центробалт. На съезде А. Г. Железняков выступил с докладом по вопросу об отношении к демократическому совещанию, по его мнению, являющемуся «новой попыткой остановить пролетариат в его борьбе». На съезде выступил за расторжение Временным правительством всех тайных договоров, заключенных царской Россией, отказ от уплаты долгов странам Антанты, поддержал перспективу социализации предприятий и земли, стоял на позиции большевиков в части перехода всей власти к Советам и к Всероссийскому съезду Советов. Был избран делегатом на Северный областной съезд Советов и делегатом от моряков Балтийского флота на II Всероссийский съезд Советов. Однако возвращаться в Петроград беглецу было опасно. Поэтому А. Г. Железняков отсиживался в финском Гельсингфорсе, куда российская полиция не смела сунуться.

Приказ Я. М. Свердлова срочно прибыть в Петроград последовал лишь в самый канун октябрьских событий. В качестве проездного документа А. Г. Железнякову оформили мандат делегата, избранного от моряков на II Всероссийский съезд Советов.