19 марта 1861 года в Нижнетагильском Входо-Иерусалимском соборе был отслужен благодарственный молебен по случаю отмены крепостного права в России. На площади перед заводоуправлением был оглашен царский манифест, после чего возникла идея возведения храма в честь святого благоверного князя Александра Невского, как символа освобождения крестьян. Инициатором строительства выступил вольноотпущенный заводской служащий Дмитрий Петрович Шорин. 1 июня 1861 года главноуправляющий заводами генерал-майор В.К. Рашет собрал служащих и купцов, где был подписан «приговор» о сооружении храма и образовании попечительского комитета из четырех человек. В документе подписались 140 человек, а Шорин был назначен ответственным за сбор пожертвований. 24 ноября 1861 года в Перми была утверждена строительная комиссия, одобрившая план и фасад будущей церкви по проекту архитектора Гирста. 5 февраля 1862 года Святейший Синод благословил начало строительства храма на Вересовой горе, которую тогда же назвали Александровской.
Строительство храма началось в 1862 году. В первые два года было уложено около 600 тысяч кирпичей. Однако была выявлена недостаточная прочность кладки, и подрядчику предложили переделать работу, что замедлило процесс. Сметная стоимость строительства составляла не менее 40 тысяч рублей серебром, но к началу работ было собрано всего 3 тысячи. Проведенные сборы дали несколько сотен рублей. В.К. Рашет внес в общий фонд 400 рублей, Павел Павлович Демидов пожертвовал тысячу. В 1871 году была организована подписка по Нижнетагильской волости, решено обложить каждого годного работника сбором по 15 копеек серебром в год. За шесть лет таким образом было собрано пять с половиной тысяч рублей. Заводовладельцы пожертвовали 500 рублей на крышу и предоставили парчу на 400 рублей для праздничных риз. Значительный вклад внес Андриан А. Густомесов, выпускник Выйского училища, проживавший в Астрахани. Он передал 500 рублей и доверенность на продажу своего каменного дома стоимостью 3500 рублей для отливки колокола. На колоколе была сделана надпись: «От служащих на заводах Павла Павловича Демидова в знак благодарности за воспитание в Выйском училище».
Иконостас храма был шестиярусным, его отделкой занимался художник Ф.Д. Топорков. Он выполнил резные работы, вызолотил херувимов, звезды, царские врата, рамы около образов, колонны, карнизы и орнаменты. Образы в церкви были выполнены тагильским живописцем В.П. Худояровым. Александро-Невская церковь была освящена 6 декабря 1877 года. На ее строительство ушло 16 лет. Церковь удачно вписана в местность и издали кажется грандиозной. По фасаду она похожа на церковь, построенную архитектором Кузьминым для русских в Париже, но тагильская церковь обошлась в 43 тысячи рублей, тогда как парижская — в миллион.
Во время гражданской войны церковь значительно пострадала, дважды была пробита снарядами. До 1931 года храм был григорианским, а в 1931–1935 годах служил кафедральным собором обновленческих архиереев. В 1937 году храм был закрыт, на дверях повесили замки. В 1940 году церковь официально закрыли, и здание использовалось как склад для дуста, затем пустовало и постепенно разрушалось.
Осенью 1988 года церковь была передана общине верующих Старой Гальянки, начались работы по возрождению храма. 15 апреля 1989 года состоялось освящение храма архиепископом Екатеринбургским и Курганским Мелхиседеком (Лебедевым). С тех пор храм действует, при нем работают воскресная школа и православная гимназия.
