Храм-колокольня во имя Святого Великомученика Максимилиана, больше известный как Большой Златоуст, был заложен в 1847 году на углу Покровского проспекта (ныне улица Малышева) и Уктусской улицы (ныне улица 8 Марта). Любопытно, что построенный храм являлся лишь частью монументального проекта известного петербургского архитектора Василия Моргана, предусматривавшего строительство грандиозного собора, схожего с Храмом Христа Спасителя. Вот роль колокольни в нем и должен был выполнять Большой Златоуст.

Однако проект оказался не по карману ни прихожанам, ни городским властям, поэтому в 1876 году удалось освятить лишь колокольню, которая и стала храмом. Здание храма выполнено в стилистике московского барокко, что также отличает его от большинства других церквей города, построенных в стиле классицизма, за исключением Вознесенской церкви.

В старом Екатеринбурге Большой Златоуст был самым высоким зданием (высота купола с крестом — 77,2 м.), имевшим 10 колоколов, среди которых особенно громогласным являлся большой праздничный колокол. Говорят, что именно из-за него Максимилиановский храм получил свое второе название. После 1876 года храм продолжал совершенствоваться: так, спустя 21 год в храме появилось отопление (до того  зимой службы здесь не велись), проведенное на средства купца Рожнова.

После прихода советской власти храм действовал еще до 1930 года, хотя в его подвале разместилось овощехранилище, а в 1922 году состоялось изъятие церковных ценностей. В 1930 году храм был взорван. На месте храма была установлена скульптурная группа, изображавшая сидящих и мило беседующих вождей,  Ленина и Сталина. Скульптурная группа продержалась ровно до ХХ съезда КПСС, когда она была демонтирована и разделена на две части. Непонятно с кем разговаривающий Ильич был установлен перед входом в ЦПКиО, а Сталин исчез в неизвестном направлении. На месте же Златоуста был поставлен памятник красному герою Гражданской войны Малышеву, который простоял здесь до 2006 года, когда было принято решение о восстановлении Большого Златоуста. Малышев был перенесен к берегу реки Исеть, а на его месте началось строительство храма.