Церковь Воздвижения Креста Господня или Крестовоздвиженская церковь расположена в районе Нижегородка, находящемся в излучине реки Белая. Строительство было начато по предложению и на средства купца Трофима Петровича Козлова, впоследствии ставшего церковным старостой. Заложение церкви состоялось 1 сентября 1892 года в нижней части уступа уфимской горы. Менее чем через год состоялось ее освящение в честь Воздвижения Животворящего Креста Господня. Строение выполнено в деревянном русском стиле, характерном для XIX - XX веков. Церковь семикупольная, купола и крыша голубого цвета, кресты выполнены из зеркального золота и вставлены в чугунную рамку.
В 1902 году были пристроены северный и южный приделы. Церковь стала трехпрестольной: главный - в честь Воздвижения Креста Господня, правый - во имя святых апостолов Петра и Павла, левый - во имя святого Николая Чудотворца. В 1920 - 1930 годы церковь состояла в Андреевской автокефалии. В 1937 году церковь была закрыта, здание использовалось под склады, общежитие. Иконостасы удалось сохранить. Внутри сохранился старинный резной четырехъярусный иконостас, чудом уцелевший в Великой Отечественной Войне, во время которой храм не прекращал свою службу, и был одним из трех действующих храмов Уфы. Образы и иконы выполнены в едином древневизантийском стиле.
У церковного алтаря был похоронен первый настоятель - протоиерей Николай Котельников и церковный староста Трофим Петрович Козлов.
Важной стороной жизни Крестовоздвиженского прихода является миссионерская деятельность. Ежегодно организовывается сплав по реке Юрюзань. Во время сплава в 2004 году в деревнях Ежовка и Сафоновка на местах разрушенных храмов были установлены кресты.
54.7333, 55.9188