The location for the Church of the Nativity of the Holy Virgin was chosen by Bishop Antonius (secular name Alexey Khrapovitsky) when he served at the Ufa cathedra in the early 20th century. The church was founded in 1901. But the construction was slow due to lack of funds, until merchant Nikifor Patokin came to help. On August 23, 1909 eight bells were hoisted to the bell tower of the new church. On the 6th of August of the same year the church was consecrated. Later a Priuytsky (Nativity) square appeared near the church.
According to some sources the construction site had been chosen much earlier in 1803.
The brick three-altar church was constructed in Eclecticism style through the donations of parish members and significant contribution of churchwarden merchant Patokin. The body of the church was topped with five domes and a wide central octangle drum. The refectory was connected with the storied bell tower. There were two side-altars: southern Michael the Archangel and northern Nicholas ones.
Vasily Lezenkov was assigned the first senior priest. In 1916 the parish consisted of 1,747 males and females. The church did not have its own land, and the priests were not entitled to any stipend.
After the 1919 revolution the building was occupied by a hospital, but the church was still operating. By the Decree of the Bashkir Central Executive Committee Presidium dated April 5, 1934 the Church of the Nativity of the Virgin was closed. By the end of April the building was given to the Medical Institute to equip a dissecting room. By that time the church property had been stolen. Nevertheless, the institute did not use the building, and in December 1935 it was given to Bashkir Cinema Company. It was planned to show sound motion pictures in the facility. The witnesses, though, claim that in 1936-37 the building was used as a prison. In October 1938 it was given to an aviation repair shop.
By the decree of city council dated June 1955 the building of the former Church of the Nativity of the Virgin was transformed into Yondoz Cinema. In this connection the dome part was destroyed, whereas partition walls inside and two annexed buildings outside were constructed additionally.
By the decree of city executive committee dated August 21, 1991 the building was given back to the church members. Father Boris Razveev was the first senior priest of the church when it was opened again. Upon the consent of archbishop Nikon, the head of Ufa Eparchy, the church was reconstructed. It was significantly extended, the alter part was enlarged, the bell tower was restored, the roof was covered with galvanized iron. In several years there was established a board of trustees, headed by K. Tolkachyov, the chairman of the Republican state council. The reconstruction, though, was suspended for some time. During the reconstruction one more wooden Church of John the Forerunner was built near the Nativity of the Virgin Church where the divine service was carried out for the period of reconstruction. During the first stage of the reconstruction a low-level bell-tower with a massive dome was constructed.
In 2003 OAO Bashkirenergo suggested to finance the final stage of the reconstruction. Apart from that the company financed land improvement of the site, further construction of legation, chapel, mosaic icon of the Holy Vergin in the bell tower and professional lighting of the whole complex. The Sofrino plant manufactured the iconostasis. In December 2004 it was installed in the church.
Upon the construction the church was transformed into the cathedral of Ufa and the whole Ufa and Sterlitamak Eparchy.