Le dévouement de l'église au saint Alexandre Nevski est lié à la miraculeuse sauvegarde de l'empereur Alexandre II après l'attentat des narodovoltsy en 1866. À l'origine, l'église était dédiée à Nicolas le Miracle-Faire, ce qui est lié à la présence à Vologda en 1556 de l'icône de Nicolas le Miracle-Faire de Velikoretsky.

Jusqu'en 1869, le principal autel de l'église était consacré à Nicolas le Miracle-Faire. La construction de l'église initiale est liée à l'arrivée à Vologda en 1556 d'une copie de l'icône de Nicolas le Miracle-Faire de Velikoretsky. Cette icône, provenant de Viatka, a été amenée à Moscou en 1555 sur ordre d'Ivan le Terrible pour être restaurée, transportée en procession à travers les rivières Viatka, Kama, Volga, Oka et Moscou. À Moscou, l'icône a été accueillie avec solennité, une copie a été faite et une chapelle de Nicolas de Velikoretsky a été fondée dans la cathédrale de Pokrov en construction sur le fossé. Le chemin de retour de l'icône vers Viatka en 1556 passait par Vologda, Veliky Ustyug et Solvychegodsk, où des copies étaient créées dans les villes et monastères. À l'origine, l'église de Nicolas le Miracle-Faire à Vologda était située sur le Vieux Marché en face du monastère d'Ilia. Avant 1612, elle a été déplacée à l'intérieur du Kremlin près de la cathédrale de Sofia, où tous les bâtiments suivants de l'église ont été construits. L'endroit où la nouvelle église a été érigée était appelé Izvest' et est devenu plus tard connu sous le nom de Montagne d'Izvest', peut-être en raison des réserves de chaux qui y étaient stockées lors de la construction du Kremlin de Vologda.

Jusqu'à la fin du XVIIIe siècle, les bâtiments de l'église de Nicolas le Miracle-Faire étaient en bois. En 1627, c'était un temple en bois avec une salle à manger. En 1698, l'église est mentionnée en lien avec un incendie, dans lequel elle a brûlé avec tous les bâtiments sur la berge de la rivière Vologda, de l'église de l'Ascension à la cathédrale de Sofia. Le bâtiment en pierre actuel de l'église a été construit dans la seconde moitié du XVIIIe siècle, mais pas plus tard qu'en 1782. En 1811, le principal autel de l'église a été réconsacré au nom de l'Image Non-Manuelle du Seigneur. Dans l'église chaude, la salle à manger, des autels supplémentaires ont été consacrés : à droite, au nom de Saint Nicolas le Miracle-Faire, à gauche, au nom du Vénérable Cyrille de Novozeretsky. Au début du XIXe siècle, en raison d'une nouvelle politique d'urbanisme, selon laquelle il était prescrit de construire des institutions administratives dans les quartiers centraux de la ville, la paroisse de l'église de Nicolas à Izvest' a fortement diminué. Après 1826, l'église est devenue sans paroisse et a été rattachée à la cathédrale, et les paroissiens ont été rattachés à l'église de Pokrov. En 1869, en mémoire de la miraculeuse sauvegarde de l'empereur Alexandre II, l'église a été réconsacrée au nom du saint Alexandre Nevski. Dans les années 1860, l'église a été réparée et réaménagée à l'intérieur, le clocher à toit en tente a été remplacé par le clocher actuel en forme d'aiguille.

Après le transfert à Vologda en 1910 du 198e régiment d'infanterie Alexandre Nevski, l'église Alexandre Nevski est devenue le seul temple militaire régimentaire de la ville.

En 1924, l'église a été fermée. Le bâtiment, nationalisé, a été utilisé comme dortoir, entrepôt, bureau de la « Glavkinoprokata » et base de ski. Pendant la guerre en 1941 et 1945, le bâtiment abritait une unité militaire. Pendant la période soviétique, l'église a beaucoup souffert, le clocher et la croix au-dessus de l'église froide ont été perdus. En 1978, l'église Alexandre Nevski a été mise sous protection d'État en tant que monument d'architecture d'importance régionale. Après la restauration dans les années 1980, le bâtiment de l'église a été transféré au musée régional d'histoire locale, et en 1997, il a été restitué à l'Éparchie de Vologda. Le premier prêtre de l'église renaissante est devenu le prêtre Andreï Pyliov. Après les travaux de restauration, le 20 novembre 1997, le jour de la mémoire du vénérable Cyrille de Novozeretsky, la première liturgie a été célébrée. Le 6 décembre 1997, le principal autel a été consacré. L'autel de Cyrille de Novozeretsky a été renouvelé après la découverte de l'icône du saint, apportée à l'église par l'une des paroissiennes.