В конце XIX в. появление православного храма в Нижегородской слободе ожидалось с большим нетерпением. В этом районе, удаленном от центра города и приходских церквей, процент старообрядческого населения был особенно высок. Это не могло не беспокоить уфимское епархиальное начальство, и предложение купца Трофима Петровича Козлова (впоследствии пожизненного церковного старосты) выстроить здесь храм на собственные средства, было встречено с большим одобрением.
1 сентября 1892 г. в нижней части уступа уфимской горы, поднимающейся над Нижегородкой, епископ Дионисий (Хитров) торжественно заложил храм. На торжестве присутствовал также уфимский губернатор Л.Е. Норд. Строительство велось необычайно споро: менее чем через год (22 августа 1893 г.) состоялось освящение храма в честь Воздвижения Животворящего Креста Господня. Спустя 10 лет возникла необходимость в расширении церкви, и в 1902 году к его северной и южной сторонам примкнули приделы. Храм стал трёхпрестольным: главный – в честь Воздвижения Креста Господня, правый – во имя св. апп. Петра и Павла, левый – во имя св. Николая Чудотворца. Впоследствии входы в приделы храма на северном и южном фасадах, а также открытые проёмы в ярусе звона колокольни были забиты. Приход церкви был самым большим в Уфе и состоял преимущественно из рабочего люда. При церкви действовало церковно-приходское попечительство, помогавшее бедным жителям Нижегородки, а во время 1 мировой войны семьям солдат, ушедших на фронт.
В 1920-30-е годы храм придерживался автокефального направления, до 1937 года здесь служил епископ Руфин (Брехов). После упорной борьбы церковь была закрыта, но не уничтожена; иконостасы повреждены не были. Здесь был склад минеральных удобрений, а во время разлива воды в реке Белой в храме было общежитие для населения Нижегородки. Богослужения возобновились в годы Великой Отечественной войны. В последующие десятилетия Воздвиженская церковь была одной из трех действующих городских церквей.
Храм - характерный образец постройки в русском стиле рубежа XIX – XX вв., характерный для десятков сельских церквей Уфимского уезда и губернии. Здание рублено из бревен «в лапу», обшито тесом и в настоящее время окрашено в белый цвет с желтой отделкой, крыша и купола голубого цвета. Двусветный четверик храма увенчан пятиглавием с крупной центральной световой главой. Кресты на храме изготовлены в Екатеринославе из зеркального стекла, вставленного в чугунные рамки. Все иконы иконостаса написаны в строго церковном духе по образу древневизантийских, на некоторых изображено старообрядческое двуперстие. С восточной стороны к храму примыкает прямоугольная алтарная апсида с двумя небольшими объёмами по бокам. Прямоугольная трапезная чуть уже ядра храма. Квадратное в плане основание колокольни развито в западном направлении дощатым пристроем, исполняющем роль тамбура. Северный и южный приделы равны по ширине четверику; двусветной является только средняя их часть. Верхние восьмигранные объёмы трёхъярусной колокольни завершены шатром с луковичной главкой. Все они прямоугольные. Значительный перепад рельефа зрительно уменьшает высоту восточного фасада здания; колокольня при этом почти не воспринимается.
В композиции выделяется центральная часть храма и прямоугольный объём апсиды с собственной вальмовой кровлей. Наиболее выразительным является южный фасад, воспринимаемый при подходе к зданию из центра города. Довольно сложное построение храма (особенно верхней его части) оставляет, тем не менее, ощущение целостности. Этому способствует чёткая трехчастная структура фасада с нарастанием форм к среднему пряслу и центральной главе. Ось входа (ныне забитого) подчеркнута небольшим треугольным фронтоном в завершении средней двусветной части придела. Окно второго света, расположенное над входом, сдвоенное. Боковые оси одинарных окон также завершены фронтонами, служащими как бы основанием малых глав. Трапезная выходит на южный фасад двумя окнами, идентичными окнам первого яруса придела. Ещё одно такое же окно прорезано в основании колокольни. Композиция северного фасада аналогична.
К полотну железной дороги (на запад) церковь обращена колокольней. Её третий ярус, звон имеет по сторонам света четыре открытых проёма со скошенными углами. Энергичная линия пилообразного карниза следует очертанию щипцов в завершении каждой грани звона. К воротам церковной ограды обращены три входа с высокими ступеньками крылец. Входы в боковые приделы оформлены двускатными козырьками на деревянных столбах, а вход в основание колокольни – пологой сегментной кровлей, над которой расположен треугольный фронтон покрытия тамбура. В интерьере центральное пространство сообщается широкими проёмами с приделами и трапезной. Верхние углы проёмов скошены, имитируя арку. Наклонные плоскости со световым восьмигранником над шелыгой образуют подобие свода. В остальных помещениях потолок плоский.
Сохранился резной четырёхъярусный иконостас. Солея с полукруглым амвоном в центре поднята на две ступени над уровнем пола; её фланкируют резные киоты по три с каждой стороны. Боковые приделы имеют собственные иконостасы. Привлекательный внешний вид церкви достигнут удачным распределением масс и разнообразием форм завершения. Декоративное убранство при этом не многосложно. Углы основных объёмов отмечены лопатками с филёнками. Уступчатый карниз, расположенный в уровне подоконника второго света, проходит по всему периметру здания. Все окна заключены в гладкие наличники с фронтоном и ушками. В тимпане фронтонов первого уровня и светового барабана помещен накладной равноконечный крест. В глухих диагональных гранях звона узкие рамочные контуры повторяют очертания открытых проёмов. Крыльцо главного входа декорировано подзором простой пропильной резьбы и глухими накладками на столбах. В интерьере сохранилась роспись стен, потолка трапезной и приделов, а также наклонных плоскостей. При переходе к световому барабану. Лестница к звону расположена в небольшом помещении в основании колокольни слева от входа. Круглые печи в настоящее время не используются. Габариты здания в плане (без крылец) – 20х29,3 м.
Первый настоятель – протоиерей Николай Алексеевич Котельников основал в 1902 году первое в Уфимской губернии училище для глухонемых детей, которое располагалось в кирпичном здании чуть выше храма. Потеряв зрение в 1907 году, Котельников был вынужден выйти за штат, оставшись руководителем училища. До революции на первом этаже здания училища находилась домовая церковь в честь священномученика Ермогена, патриарха Московского и всея Руси. В советское время в помещении домовой церкви был устроен спортзал. Сейчас там планируется размещение епархиального музея. Глухонемые дети покинули это здание только в середине 1990-х годов, когда оно пришло в аварийное состояние.
Силами православного братства здание «возвращено к жизни». Сейчас здесь находятся Уфимский центр дистанционного обучения православного Свято-Тихоновского гуманитарного университета, Центр Православной педагогики «Преображение», воскресная школа, церковная библиотека и православное братство. В соседнем здании работает иконостасная мастерская. Важной стороной жизни Крестовоздвиженского прихода стала миссионерская деятельность. Ежегодно организовывается сплав по реке Юрюзань. Во время сплава в двух деревнях (Ежовка и Сафоновка) на местах разрушенных храмов установлены кресты (в 2004 г.) и служится Литургия. Первый настоятель – протоиерей Николай Котельников и церковный староста Трофим Петрович Козлов были похоронены у алтаря. Их могилы существуют и поныне.
