Рождество-Богородицкий храм расположен по улице Кирова, 101 (бывшая Приютская), место было выбрано епископом Антонием в 1903 году. Из-за нехватки средств строительство затянулось, пока на помощь не пришел уфимский меценат, купец Никифор Миронович Патокин.

23 августа 1909 г. на колокольню нового храма были подняты колокола. Всего их было восемь. Самый большой весил 50 пудов 35 фунтов, самый маленький - 10 фунтов. Церковь была кирпичной, с такой же трехъярусной колокольней и деревянным одноглавым куполом, обитым железом и окрашенным в кирпичный цвет. На куполе колокольни и алтаря были железные кресты, бронзированные через огонь, крыша крыта железом и окрашена в зелёный цвет. Полы асфальтовые, края цементные. Длина церкви, считая и колокольню, 206,5 саженей, наибольшая ширина 10,5 саженей.

6 сентября 1909 г. преосвященным Нафанаилом, епископом Уфимским и Минзелинским, было совершено освящение храма Рождества Пресвятой Богородицы. Первым настоятелем был назначен Василий Григорьевич Лезенков. Церковь действовала в 20-е и 30-е годы.

Постановлением Президиума БашЦИК от 5 апреля 1934 года церковь была закрыта, храм был передан «Башкино» в декабре 1935 г. для установления звукового кино. В дальнейшем передан в авиамастерские, согласно Постановления Горсовета от 16 октября 1938 г. Постановлением Уфимского Горсовета № 224 от 21 июня 1955 г., здание бывшей Рождество-Богородицкой Церкви было передано под кинотеатр, который получил наименование «Йондоз». Были произведены большие разрушения, уничтожена купольная часть. Наполовину снесены опорные столбы. Кинотеатр находился в помещении храма до 1991 г.

Постановлением решения Горисполкома №14/608 от 21 августа 1991 г. здание возвращено Епархиальному управлению.

Первым настоятелем после открытия храма был назначен Развеев Борис Борисович. Началось восстановление храма.

В 2002 году была предпринята новая попытка продолжения строительства. Однако откликнулось на призыв епархии только Управление по исполнению наказаний РБ в лице генерала-майора Шалыгина. Именно он нашел возможным предоставить 50 добровольцев из числа осужденных, которые подручными средствами отбили внутри храма всю, пришедшую уже в негодность, штукатурку.

Дело сдвинулось в 2003 году, когда ОАО «Башкирэнерго» вышло с предложением профинансировать завершение работ по реконструкции храма. Было особенно отрадно, что руководство Башкирэнерго подошло к этой стройке с душой.