Храм Александра Невского был построен в 1886 году. Храм Александра Невского, первый в Туле храм, построенный в русско-византийском стиле. До этого в тульской архитектуре господствовал классицизм. Церковь Александра Невского имела четыре небольшие декоративные главки и одну большую главу в виде мощного восьмигранного светового барабана со шлемовидным завершением, увенчанным маковкой на маленьком барабанчике. Над папертью находилась оригинальная, с плоским куполом, звонница. Иконостасы, резные дубовые. Внутри храм окрасили масляной краской. Священные изображения поместили только в куполе. В нижней части церкви были начертаны изречения из Евангелия и Апостола. Прихожанами храма стали верующие Петропавловского храма и церкви Николы на Ржавце. В храме разместилось два предела, Евфимия Нового и мученицы Евдокии. Церковно-приходская школа при храме Александра Невского была открыта в 1889 году в память 900-летия крещения Руси. Тысячу рублей серебром на устройство школы завещал скончавшийся в мае 1888 года коллежский секретарь Н. А. Давыдов. Для школы был построен специальный деревянный дом, крытый железом. Впоследствии основной денежный фонд на содержание школы предоставлял фабрикант-самоварщик А. С. Баташев. В 1892 году в школе обучались 58 мальчиков. На средства попечительства при школе была организована библиотека, насчитывавшая к концу века 200 книг для чтения и 250 учебников. Наиболее бедные учащиеся обеспечивались одеждой, а в неурожайные годы горячими обедами. Всем учащимся предоставлялись учебники и учебные пособия. В 1896 году, в память коронации Николая II, попечительство открыло при храме библиотеку-читальню для взрослых, в фондах которой имелось до 600 книг религиозно-нравственной и исторической тематики. Библиотека-читальня была создана на деньги, завещанные членом попечительства П. П. Рудневым. С 1887 по 1897 годы в храме служил священномученик Алексий Бельковский.
В 1902 году приходское попечительство пристроило к зданию церковноприходской школы отдельную пристройку для обучения девочек и пригласило для них учительницу рукоделия. В 1908 году в школе было 60 учениц. В 1905 году к храму сделали две пристройки по обеим сторонам паперти. В одной разместили ризницу и библиотеку, в другой складывали различную церковную утварь. При храме действовала богадельня, открытая в 1891 году на средства, завещанные купцом А. П. Молчановым. В ней на полном содержании жили шесть неимущих престарелых женщин. В обязанности призреваемых входила забота о чистоте в храме и в богадельне. Богадельня представляла собой дом из соснового леса размером примерно 14 на 7 метров, разделенный теплым коридором на две половины. В одной помещались призреваемые, в другой кухня с подвалом. Церковь дала название двум объектам на карте Тулы. В 1906 году по постановлению городской Думы «безымянный переулок в местности, идущей от городского парка до соединения с Пушкинской улицей, назван Александро-Невским». Интересно, что на плане города 1891 года этот «переулок» вовсе не безымянный, а числится как «Беляевская улица». Плац-парад стал именоваться Александро-Невской площадью. Позже Александро-Невский переулок получил статус улицы, а в 1923 году Александро-Невская улица была переименована в улицу Софии Перовской. По крайней мере, ещё в 1925 году название «Александро-Невская площадь» сохранялось. Позже оно было утрачено. В 2008 году решением Тульской городской Думы площади рядом с храмом было возвращено имя Александра Невского.
Пока не удалось установить точную дату, когда Александро-Невскую церковь закрыли в первый раз. Но 25 апреля 1924 из ВЦИК в Тульский губисполком был направлен документ, в котором говорилось о поступившей во ВЦИК жалобе группы верующих, имевшей по договору в пользовании Александро-Невский храм, о закрытии этого храма. Лишь 16 февраля 1925 года тульские власти наконец-то ответили ВЦИКу. В ответе говорилось: «Тулгубисполком сообщает, что закрытие Александро-Невской церкви носило временный характер, вызванный тем, что эта церковь все время являлась пристанищем кучки самых махровых монархистов во главе с бывшим Председателем Тульского Союза Русского народа, бывшим Городской Головой Любомудровым, которым нужна была церковь лишь для прикрытия антисоветских работ. В настоящее время Александро-Невская церковь передана группе верующих, внушающей доверие и лояльной советской власти». А по решению президиума Мособлисполкома от 16 февраля 1930 года Александро-Невскую церковь закрыли окончательно и её здание было передано 12-й трудовой школе. В дальнейшем в храме размещался хлебозавод № 4. В 1991 году здание храма было поставлено на госохрану в качестве памятника истории и культуры регионального значения.
В марте 2003 года храм передали верующим. Первоначальный облик храма не сохранился. Были утрачены четыре малых главы, а центральный купол лишился своего изящного завершения. В каждом из трех алтарей стояли печи. Фрески не сохранились, потому что стены храма были облицованы плиткой. 14 октября 2005 года над храмом был водружен крест. В настоящее время внешний облик храма был восстановлен, кроме четырёх малых глав.
