Долгие годы на месте будущей церкви был пустырь, на котором располагался городской выгон. Затем здесь выросла часовня. Инициатива ее постройки принадлежала челябинскому мещанину Кутыреву. Надо отметить, что на строительство часовни средства собирались очень долго. Часовня была воздвигнута в память об убитом народовольцами царе Александре II. А Александр Невский — это святой покровитель царя.
После строительства Самаро-Златоустовской железной дороги город бурно развивался, население его стремительно росло. Решено было перестроить часовню в церковь. Но опять возникла проблема нехватки средств. Между тем был решен вопрос об архитектурном облике здания. Проект церкви выполнил академик А.Н. Померанцев, в то время уже признанный мастер, его авторству, например, принадлежит проект Верхних торговых рядов в Москве — ныне ГУМ.
Хотя средств на постройку еще было недостаточно, 22 июня 1907 года храм все-таки был заложен. Деньги на постройку жертвовали многие организации и частные лица, в том числе Николай II. Самое крупное пожертвование сделал челябинский мукомол М.П. Архипов. Главный престол был освящён 4 декабря 1911 года, а из 2-х алтарных приделов до революции был достроен и освящён только один — правый, во имя Святого Николая Чудотворца. Дело в том, что странным образом средств на устройство придела опять не хватило. 13-тиглавая церковь построена из красного кирпича. Имеет один этаж с подвалом. Росписи внутри храма были выполнены мастерской В.И. Ощепкова.
В 1922 году из церкви были изъяты все ценности, сняты купола, кресты и шатер колокольни. В 1930 году церковь закрыли.
В дальнейшем здесь располагались: газетный цех типографии «Челябинский рабочий», картинная галерея, планетарий, шахматный клуб. В начале 1980-х годов здание было передано Челябинской филармонии.
К 250-летию Челябинска храм был отреставрирован, для этого специально были найдены чертежи Померанцева. Работа по реставрации, проведенная архитектором К. Гусаровым, — тонкая и кропотливая. Полностью обновлен фасад. Заново был открыт секрет цепной и крестовой кладки кирпича. Восстановлены шатер, купола, а впоследствии, к 1000-летней годовщины Крещения Руси, были установлены и кресты. Золочённые кресты церкви Александра Невского были первыми крестами, установленными в Челябинской области после долгого периода разрушения церквей и выглядели в глазах южноуральцев настоящей диковинкой. Ведь в то время на Троицком храме не то что крестов — куполов не было!
Преобразился интерьер здания — изящная в позолоте лепка, стены украшены панно из мрамора, яшмы, змеевика, лабрадорита. Панели и полы изготовлены из цельных пород дерева. Заново сделаны оригинальные оконные рамы, двери. Важно, что здание было перестроено с учетом всех условий, необходимых для установки органа, включая даже специально разработанную систему кондиционирования воздуха. В 1987 году орган был установлен. Изготовили его мастера немецкой фирмы «Германн Ойле». Инструмент насчитывает 2504 трубы, 37 регистров, три мануала и педальную клавиатуру. Очень скоро орган получил высокую оценку музыкального сообщества. Многие исполнители считают его одним из лучших в России и Европе. Органный зал, вмещающий 300 зрителей, играл заметную роль в музыкальной жизни города.
Еще с 1990-х годов велись дискуссии по поводу возвращения здания верующим. В августе 2011 года, несмотря на протесты музыкального сообщества и многих горожан, здание было передано в собственность Русской Православной Церкви. Последний концерт в Органном зале состоялся 27 ноября 2013 года. Решено было перенести орган в здание бывшего кинотеатра «Родина».
С 2014 года храм действует, в нем проходят богослужения, одновременно ведутся ремонтные работы — восстанавилвается внутреннее убранство и первоначальная планировка. С ноября 2016 года начались противоаварийные работы по укреплению фундамента с целью остановить его проседание. Проект реставрации разработали ученые из Екатеринбурга и Москвы. В течение двух лет проводились исследовательские работы, 12 августа 2016 года получено разрешение на проведение противоаварийных и демонтажных работ от Госкомитета охраны объектов культурного наследия Челябинской области.
На следующем этапе строители восстановят воздушные связи между арками, которых сейчас нет. Это является одной из возможных причин деформации здания. До конца года планируется восстановить все воздушные связи в арочных проемах или создать новые там, где это понадобится. В будущем году предполагается починка кровли, снос перегородок и стен в цокольном этаже, перепланировка помещения, создание гидроизоляции, обустройство кольцевой дренажной системы вокруг здания. Эти защитит основание церкви от дальнейшего разрушающего воздействия грунтовых вод.
По плану на реставрацию храма понадобится от двух до трех лет года. Финансирование работ производит частный инвестор. Богослужения в храме продолжаются, он всегда открыт для верующих.
