Деревянная церковь воздвигнута близ Бирского тракта и железной дороги в 1892-93 гг. для духовного окормления жителей Нижегородской слободы, бывших раскольников. Скопление большого количества старообрядцев на окраине города нежелательно было ни епархиальному начальству, ни городскому. Сооружалась церковь в основном на средства купца-храмоздателя Трофима Петровича Козлова. 1 сентября 1892 г. в нижней части уступа уфимской горы, поднимающейся над Нижегородкой, епископ-миссионер Дионисий (Хитров) торжественно заложил храм.

Строительство велось споро и быстро, уже 22 августа 1893 г. семиглавый храм с крестами необычного вида – из зеркального стекла, вставленного в чугунные рамки, был освящён в честь Воздвижения Животворящего Креста Господня. Архитектура храма – хороший деревянный русский стиль, характерный для десятков сельских церквей Уфимского уезда и губернии. По имени храма три близлежащие уфимские улицы получили имена Воздвиженские: Большая, Средняя и Малая; более известна Большая Воздвиженская (Лесопильная).

Вторым человеком, коему храм обязан своим существованием, – Николай Алексеевич Котельников. Он стал благодетелем и строителем близ церкви в 1902 г. первого и единственного в Уфимской губернии училища для глухонемых детей. Козлов и Котельников похоронены у южной стороны алтаря храма. Спустя 10 лет возникла необходимость в расширении церкви, и в 1902 г. к его северной и южной сторонам примкнули приделы. Храм стал трёхпрестольным: правый престол – во имя св. апп. Петра и Павла, левый – во имя св. Николая чудотворца.

В советское время, после упорной борьбы церковь всё же была закрыта в 1937 году, но, к счастью, не уничтожена. Здесь были склады, общежитие; иконостасы повреждены не были.

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

Важной стороной жизни Кресто-Воздвиженского прихода стало миссионерство, как среди горожан, так и посредством сплава по рекам Белой и Юрюзани. С 1999 г. устраиваются летние православные лагеря по сельским приходам Уфимской епархии.