On September 21, 1990, Metropolitan of Moscow and All Russia Alimpy [ru] consecrated a place for the construction of the church near Bestuzhev Street in Zayeltsovsky District.

The walls of the cathedral were built by parishioners Roman Bekrenyov and Boris Kokorin.

The auxiliary workers who participated in the construction were also parishioners: A. Bozhenkov, F. A. Ustinov, V. E. Shevyakov, N. A. Gaevsky, D. Gorenko, P. N. Lebedev; the Borisov brothers fenced the construction site with a metal fence and laid the cable.

Old Believer Alexander Chetvergov (later Metropolitan Andrian [ru]) from Kazan created the project of the iconostasis and built it himself, he also painted five icons for the church, gilded all the crosses of the cathedral and, in addition, on September 17, 1999, set the cross of the central dome.

On September 19, 1999, Metropolitan Alimpy consecrated the Cathedral of the Nativity of the Blessed Virgin Mary.