Нынешний главный храм Уфы наследует этот высокий статус от своего предшественника — Воскресенского собора, на сегодняшний день возрождённого и тоже сохранияющего кафедральное значение. Строительство будущей церкви Рождества Богородицы было запланировано в конце ХIХ столетия, о чём свидетельствуют сохранившиеся чертежи городской застройки. Место для него выбрал сам Антоний, тогдашний епископ Уфимский. Поставить храм — дело долгое и дорогостоящее, а необходимых средств для будущего собора, как всегда, недоставало. Лишь в 1901 году состоялась торжественная церемония закладки новой церкви, после чего наконец-то развернулись основные строительные работы. Это стало возможным благодаря действенной помощи местного купца, главного Уфимской городской думы Никифора Патокина. Когда строительство начало явно пробуксовывать, грозя выродиться в очередной российский долгострой, Никифор Миронович выделил деньги, необходимые для возведения здания основного объёма храма и колокольни, для которой он закупил четыре пары «звонов». И работа сразу закипела. По задумке епископа Антония будущий кафедральный собор должен был расположиться на восточной стороне улицы Приютской. Она была названа в честь православного детского приюта, открытого здесь в 1849 году благодаря инициативе графа Строганова, председателя общероссийского Главного комитета попечительства о детских учреждениях общественного призрения. Приютская улица, подобно реке в море, «вливалась» в городскую площадь, большой квадрат которой окружал бы храм Рождества Богородицы, став его присоборной территорией. Алексей Храповицкий — так в миру звался архиерей — уготовил главному храму Уфы место, на Приютской площади.
Постройка главного городского собора, несмотря на финансовую поддержку мецената, растянулась вплоть до 1909 года. В ходе работ местные каменщики использовали некоторые технологические идеи, в частности, кирпичную кладку, уже апробированные при недавнем строительстве Никольской церкви 1897 года, возведённой возле железнодорожного вокзала. Рождественский храм получился нарядным: зелень кровли на крыше красиво гармонировала с покрытыми бронзой крестами его массивных куполов. Кирпичное здание основного объёма украшала трёхъярусная колокольня, а купол, хотя и был сработан из дерева, зато искусно обит железом и также окрашен «под кирпич». 23 августа всем миром на колокольню новоиспечённого собора поднимали колокола. Из восьми новых «звонов» наиболее миниатюрным был десятифунтовый. Зато самый массивный потянул на 50 пудов и 35 фунтов. Дар купца Патокина оказался «голосистым» — колокола были слышны далеко окрест. Всё было готово к приёму богомольцев, вплоть до асфальтовых полов, закреплённых по краям цементным раствором. Места в церкви хватало: общая длина её здания вместе с колокольней составляла 206,5 саженей при максимальной ширине в 10,5 саженей. С учётом того, что одна сажень — единица длины, общеупотребительная в России тех лет, — составляла 2,13 метра, это был вполне вместительный храм для своего времени.
6 сентября 1909 года новый кафедральный собор Уфы был освящён. Церемонию провёл епископ Уфимский и Мензелинский Нафанаил, в миру Николай Захарьевич Троицкий. Северный придел собора освятили во имя святителя Николая Чудотворца; южный — во имя Архистратига Михаила. Первым настоятелем храма был назначен священник Василий Лезенков. По окончании строительства собора оживилась жизнь на окружавшей его Приютской площади, стал быстро формироваться церковный приход. В 1916 году он насчитывал уже 1747 человек мужского и женского полов; земельных владений у храма не было, и жалованье священники поначалу не получали. Собор Рождества Богородицы стал последним православным храмом Уфы, построенным в дореволюционный период. Когда грянули революционные события 1917 года, храм оставался действующим. В 1919-м году в помещениях собора был размещён госпиталь для раненых и выздоравливающих, при этом церковная жизнь продолжалась, как прежде.
Когда-то глаза прихожан собора радовали золочёные хоругви и кресты, уникальные старинные иконы, резные аналои, сработанные из крепкого дуба, посеребренные подсвечники. Все они исчезли в советскую эпоху, когда в Уфе один за другим стали закрываться православные храмы. В этот период властями насаждалось обновленчество, особенно активно этот процесс шёл начиная с 1920-х годов. Появились священники и епископы нового толка, сеющие раскол в рядах православных общин. Храмы захватывались духовенством, пошедшим на сделку с советской властью, но последующее их массовое закрытие красноречиво свидетельствовало о провале этой авантюры. С закрытием в Уфе кафедрального собора стало окончательно ясно: идеологические игры большевиков потерпели крах, и отныне устанавливалась эпоха жёсткого, воинствующего атеизма. Священникам и прихожанам ценой немалых усилий удавалось защитить родной храм вплоть до 1934 года. 5 апреля Президиум БашЦИК постановил закрыть Рождественско-Богородскую церковь, после чего началось её планомерное разорение, покуда решался вопрос, для каких хозяйственных нужд можно приспособить освободившиеся помещения. В итоге было решено передать храм медицинскому институту — под анатомическую клинику. По причине бюрократической волокиты анатомическая клиника в опустевшее здание так и не переехала, и оно продолжало пустовать вплоть до окончания следующего года. Только в декабре 1935 года храм передали в ведомство «Башкино». Однако предыдущая история повторилась: надежды работников кинофикации оборудовать в церковном помещении установку для демонстрации звукового кино, первенцем которого в СССР стала драма «Путёвка в жизнь», не спешили воплощаться в жизнь. По некоторым сведениям, в 1936 году вместо медиков и киношников в храм пришли сотрудники НКВД. Эта в высшей степени серьёзная организация развернула в здании свою тюрьму, но уже в следующем, 1937 году по каким-то причинам освободила помещения. В октябре 1938 года здание использовалось в качестве склада. Власти стремились искоренить само упоминание о православии, Боге и религии. Однако невозможно вычеркнуть из истории города важную и существенную её часть, и даже когда церкви уничтожались, либо, подобно храму Рождества Богородицы, использовались не по назначению, люди помнили их прежние имена, звоны колоколов и кресты, осенявшие город светлой благодатью.
Грянула Великая Отечественная война и принесла уфимским храмам новые испытания. По рассказам священников нынешнего, теперь уже кафедрального собора, некоторое время в его здании размещался призывной пункт, откуда новобранцев увозили на военную службу. Любое нецелевое использование здания и его помещений неизменно наносит ему серьёзный вред. В особенности это стало заметно, когда в храме Рождества Богородицы начли работать авиамастерские. Они принадлежали эвакуированному в Уфу Куйбышевскому моторостроительному заводу, оборонному предприятию, которое не должно было останавливаться ни на день. Однако многие крупные детали и узлы самолётов, подлежащих здесь ремонту, попросту не вписывались во входные порталы церкви. Поэтому был расширен главный вход, и можно сказать, что храму ещё повезло с новыми «хозяевами» здания: в церквях, где в годы войны работали танковые мастерские, стены просто проламывали, чтобы транспортировать внутрь здания повреждённые стальные машины.
В послевоенные годы здание храма постепенно перевели на «мирные рельсы». В июне 1955 года Уфимский городской совет постановил передать помещение бывшей Рождественско-Богородицкой церкви государственной организации «Башкино». В здании был открыт кинотеатр «Йондоз», «Звезда». Первым кинофильмом, который был показан в новом кинозале в 1958 году, стала лента режиссёра Сергея Параджанова «Первый парень». В жизни кинотеатра бывали разные времена, а началась она с варварской переделки церкви. «Реконструкция» здания полностью лишила его купольной части, колокольни и двух пристроек. Были заменены все строительные перекрытия, установлены массивные опорные столбы и аляповатый портик при входе, в духе помпезного сталинского ампира. Внутри здания, как в любом кинотеатре, строители оборудовали кассу, фойе и главное помещение — зрительный зал.
По рассказам горожан, позади новоиспечённого кинотетра на некоторое время раскинулся пустырь, однако свято место пусто не бывает: в воскресные дни здесь обосновалась городская «толкучка», как в советские времена нередко именовали стихийные вещевые рынки — «барахолки». Сюда потянудись люди со всей Уфы, а заодно посещали и кинотеатр. Шло время, менялось и отношение к религии. Между тем члены православной общины неустанно требовали у властей вернуть им храмы. Немало писем поступило к городскому руководству и по поводу храма Рождества Богородицы. Сыграло свою роль и то печальное обстоятельство, что большинство уфимских церквей к началу 1990-х годов были закрыты и разорены. Рано или поздно количество обращений верующих к властям должно было привести к неименуемой подвижке ситуации, что и произошло летом 1991 года. Поначалу в здании прекратили демонстрацию киносеансов, а 21 августа уфимский горисполком постановил возвратить здание храма Рождества Пресвятой Богородицы прихожанам.
4 сентября здание уже бывшего кинотеатра было передано РПЦ. Храм стали восстанавливать всем миром. Благодаря неутомимой работе назначенному в храм настоятеля — отца Бориса Развеева и силами прихожан, была организована уборка мусора на прихрамовой территории, после чего началась капитальная реконструкция здания храма; удалось восстановить всю её купольную часть, надстроить недостающие ярусы колокольни, настелить железную кровлю и расширить окружающую территорию. В 1992 году о храме Рождества Пресвятой Богородицы заговорили уже во всей России: здесь стали мироточить сразу несколько старых икон, о чём написала центральная пресса. После этого знаменательного случая власти стали активнее помогать восстановлению и реконструкции храма, но всё равно восстановительные работы продолжались ещё много лет. В 2016 году Патриарх Московский и всея Руси Кирилл в ходе своего визита в Республику Башкортостан совершил Божественную литургию в Богородице-Рождественском храме и присвоил ему статус кафедрального собора.
