Il est avéré qu'il existait au début du XVIe siècle une église de bois dédiée à « la grande martyre Barbe », près de l'étang noir (à l'emplacement actuel du square de l'Étang-Noir). Une église de pierre à une coupole la remplace en 1757. Elle est construite par les soins de Vassili Denissov, greffier du consistoire ecclésiastique de Nijni Novgorod (selon d'autres sources, par Chouchpanov, au service des Stroganov) sous l'évêque Benjamin Ier (Poutsek-Grigorovitch) ou l'évêque Théophane (Tcharnoutski)[1].
À la fin du XVIIIe siècle ou au début du XIXe, l'on ajoute une trapeznaïa avec des absides et un clocher, sous l'épiscopat de Benjamin II (Krasnopevkov). Une église chauffée pour l'hiver est installée en 1832 grâce aux dons de Maria Zoubova, de la classe des marchands. L'église a trois dédicace: la principale en l'honneur de Notre-Dame de Vladimir; celle de l'abside de droite en l'honneur des martyres Sophie (son nom signifiant la Sagesse), Véra (la Foi), Nadejda (l'Espérance) et Lioubov (la Charité); celle de gauche en l'honneur de la grande martyre Barbe (ou Barbara). L'on construit en 1861 une maison de bois et une maison de brique pour le clergé[1].
Enа 1916, la paroisse compte 400 hommes et 980 femmes. Après la révolution d'Octobre, la paroisse est forcée de conclure un accord, le 15 novembre 1918, pour la municipalisation de ses biens en échange d'un « usage perpétuel ». Après de vives campagnes d'athéisme menées par les autorités communistes, la paroisse compte encore 363 personnes enregistrées en 1930. Le 20 août 1932 le soviet de district fusionne la paroisse Saint-Nicolas (de la grand-rue de l'Intercession), supprimée, à celle de Sainte-Barbe. Saint-Nicolas avait auparavant absorbé les paroisses des églises fermées Saint-Alexis, Saint-Georges et Saint-Tikhon[1].
En 1937 pendant les grandes purges staliniennes, les desservants de l'église Sainte-Barbe sont arrêtés: le prêtre Constantin Vassilievitch Vesselitski, le prêtre Alexandre Nikolaïevitch Nikolski, le protoprêtre Evgueni Nikanorovitch Iakovlev, le diacre Alexeï Vsevolodovitch Ivanov et le prêtre acolyte servant de chantre, Sergueï Ivanovitch Zefirov. Ils sont tous accusés de participer à la « filiale de Gorki (nom à l'époque de la ville) de l'organisation ecclésiale fasciste fondée par les métropolites Serge Starogodski et Théophane Touliakov ». Le 4 avril 1937, le Père Constantin Vesselitski est fusillé et tous les autres, le 17 décembre suivant. Le président du conseil paroissial (marguillier), V.I. Arefiev, échappe à la condamnation à mort[1].
Le 14 août 1938, le soviet du district de Jdanov de la ville décide de fermer l'église au culte. La paroisse est aussitôt supprimée. L'église est transformée en bureaux administratifs, puis en janvier 1940 on y place des archives[1].
Le 22 juillet 1958 le soviet municipal décide de démolir l'église à cause de son insalubrité[1].
