Много лет на месте будущей церкви находился пустырь, где был городской выгон. Позже здесь появилась часовня, инициатором строительства которой стал челябинский мещанин Кутырев. Средства на её возведение собирались долго. Часовня была построена в память о царе Александре II, убитом народовольцами, а Александр Невский был его святым покровителем.

После открытия Самаро-Златоустовской железной дороги город начал быстро развиваться, и население росло. Было решено перестроить часовню в церковь, но снова возникли трудности с финансированием. Вопрос архитектурного облика здания был решён: проект церкви выполнил академик А.Н. Померанцев, известный своими работами, такими как проект Верхних торговых рядов в Москве, ныне ГУМ.

Несмотря на нехватку средств, 22 июня 1907 года храм был заложен. Деньги на строительство жертвовали различные организации и частные лица, включая Николая II. Самое крупное пожертвование сделал челябинский мукомол М.П. Архипов. Главный престол освятили 4 декабря 1911 года, а из двух алтарных приделов до революции был достроен и освящён только правый, во имя Святого Николая Чудотворца, так как средств снова не хватило. Церковь, построенная из красного кирпича, имеет один этаж с подвалом. Росписи внутри выполнила мастерская В.И. Ощепкова.

В 1922 году из церкви изъяли все ценности, сняли купола, кресты и шатер колокольни. В 1930 году церковь закрыли.

Позже здесь размещались: газетный цех типографии «Челябинский рабочий», картинная галерея, планетарий, шахматный клуб. В начале 1980-х здание передали Челябинской филармонии.

К 250-летию Челябинска храм был отреставрирован. Для этого нашли чертежи Померанцева. Архитектор К. Гусаров провёл тонкую и кропотливую работу, обновив фасад и восстановив шатер и купола. К 1000-летию Крещения Руси установили кресты. Золочённые кресты церкви Александра Невского стали первыми в Челябинской области после долгого периода разрушения церквей.

Интерьер здания преобразился: стены украсили панно из мрамора, яшмы, змеевика, лабрадорита, а панели и полы сделали из цельного дерева. Были восстановлены оригинальные оконные рамы и двери. Здание перестроили с учётом установки органа, включая специально разработанную систему кондиционирования. В 1987 году установили орган, изготовленный немецкой фирмой «Германн Ойле». Он насчитывает 2504 трубы, 37 регистров, три мануала и педальную клавиатуру. Орган получил высокую оценку музыкального сообщества и стал одним из лучших в России и Европе. Органный зал, вмещающий 300 зрителей, играл важную роль в музыкальной жизни города.

С 1990-х годов обсуждалось возвращение здания верующим. В августе 2011 года, несмотря на протесты музыкального сообщества и горожан, здание передали Русской Православной Церкви. Последний концерт в Органном зале прошёл 27 ноября 2013 года. Орган перенесли в здание бывшего кинотеатра «Родина».

С 2014 года храм действует, в нём проходят богослужения, ведутся ремонтные работы, восстанавливается внутреннее убранство и первоначальная планировка. С ноября 2016 года начались противоаварийные работы по укреплению фундамента для остановки его проседания. Проект реставрации разработали учёные из Екатеринбурга и Москвы. В течение двух лет проводились исследования, и 12 августа 2016 года было получено разрешение на проведение противоаварийных и демонтажных работ от Госкомитета охраны объектов культурного наследия Челябинской области.

На следующем этапе строители восстановят воздушные связи между арками, что может быть причиной деформации здания. До конца года планируется восстановить все воздушные связи в арочных проёмах или создать новые. В следующем году предполагается починка кровли, снос перегородок и стен в цокольном этаже, перепланировка помещения, создание гидроизоляции и обустройство кольцевой дренажной системы вокруг здания. Это защитит основание церкви от разрушительного воздействия грунтовых вод.

На реставрацию храма потребуется от двух до трёх лет. Финансирование работ осуществляет частный инвестор. Богослужения в храме продолжаются, он всегда открыт для верующих.