Die große Backsteinkirche im klassizistischen Stil wurde an der Stelle der 1672-1681 erbauten Steinkathedrale errichtet. Der Bau begann 1810, die Warmkirche wurde 1837 fertiggestellt, und die Hauptkirche 1841. In der Warmkirche befanden sich die Altäre des Athanasius von Alexandria und der Paraskeva Freitag, während die Seitenaltäre der Hauptkirche dem Stephanus und der Gottesmutter von Kiew gewidmet waren.

Der Hauptkörper des Gebäudes stellte einen Würfel mit einer großen Rotunde, einer Warmkirche und Seitenaltären dar, die mit kleinen Kuppeln abgeschlossen waren. Der freistehende mehrstöckige Glockenturm im eklektischen Stil wurde 1865-1875 erbaut. In der Kathedrale wurde das wundertätige Bild des Heiligen Nikolaus aufbewahrt, das aus Holz geschnitzt und 1415 offenbar wurde. Die Kirche befand sich auf dem Gipfel des Kathedralenbergs (im 17. Jahrhundert bekannt als Samorod-Berg) an der Mündung des Flusses Mzna in die Zusha.

„Haus des Heiligen Nikolaus“ in Mzenzk war eine der ältesten Kirchen der Region Orjol und existierte wahrscheinlich bereits im 12. Jahrhundert. Die ersten dokumentarischen Erwähnungen stammen aus dem Jahr 1625. Die Holzkirche befand sich im Zentrum des Mzenker Kremls, bekannt als der Gehauene Stadt. Im Kreml befand sich auch die Holzkirche der Paraskeva Freitag. 1672 begann der Bau der Steinkathedrale mit Glockenturm an der Stelle der baufälligen Holzkirche, der bis 1681 dauerte. 1689 wurde hier der Bauleiter der Kirche beigesetzt. 1757 wurde die Kathedrale stark durch ein Feuer beschädigt, das auch die Reste der Holzkfestung und die Kirche der Paraskeva Freitag vernichtete, die dann an einem anderen Ort wieder aufgebaut wurde. In diesem Jahr wurden die alte Warmkirche und der Glockenturm abgerissen, und der Bau neuer begann. Bis 1773 wurde eine größere Warmkirche mit einem Altar zu Ehren des Athanasius von Alexandria und ein hoher Glockenturm im Barockstil errichtet.

Zu Beginn des 19. Jahrhunderts war die alte Kathedrale baufällig und wurde für die Gläubigen zu klein. Ein neues Projekt wurde dem Architekten Abraham Ivanovich Melnikov in Auftrag gegeben. Die neue Kathedrale wurde 1810 auf dem Gelände zwischen der alten Kathedrale und dem Standort der Freitagkirche errichtet. 1837 wurde die warme Kirche mit zwei Altären fertiggestellt: dem des Heiligen Athanasius von Alexandria und dem der Heiligen Paraskeva Freitag. Die alte Kathedrale wurde abgerissen, nur der Glockenturm blieb stehen, und die neue Kirche wurde durch die Altäre erweitert, die 1841 fertiggestellt wurden. In den Jahren 1844-1845 wurde die Kathedrale von den Künstlern Tikhon und Nikolai Bogdanov bemalt. 1859 wurde das Gelände von einer Steinmauer umgeben. 1865 begann der Bau eines neuen Glockenturms, der zehn Jahre später abgeschlossen wurde.

Die größte Glocke wog 718 Pud und wurde in der Moskauer Fabrik Smagin gegossen. Am Glockenturm hing auch eine alte Ankündigungsglocke mit der Inschrift: „7188 (1680) Februar am 2. Tag, des großen Herrschers Ankündigungsglocke in Mzenzk“.

Die Hauptheiligkeit der Kathedrale war das wundertätige Bild des Heiligen Nikolaus, zu dem jährlich Hunderttausende von Pilgern kamen. Der Legende nach kam das Bild 1415 auf einem steinernen Kreuz gegen den Strom des Flusses Zusha nach Mzenzk. Die Kathedrale zog die Aufmerksamkeit von Reisenden auf sich, darunter der Fürst I.M. Dolgorukov und der Philologe I.I. Sreznevsky. N.S. Leskov erwähnt in seinem Werk, dass sein Held Levsha sich vor einer wichtigen Arbeit zum wundertätigen Bild begab.

Die Kirche wurde in den 1930er Jahren gesprengt, und die Reste ihrer Wände standen bis Anfang der 1960er Jahre. 1996, zum 850. Jubiläum von Mzenzk, wurde an ihrer Stelle eine Backsteinkapelle errichtet.