L'église baroque de Saint Nicolas est considérée comme l'une des plus vénérées parmi les fidèles, car au cours de ses trois siècles d'histoire, elle n'a été fermée que pendant trois ans. Le temple a résisté pendant l'occupation allemande et les combats pour la libération de la ville. Son prédécesseur en bois avait une grande importance pour l'État et la politique, car à l'époque, il était nécessaire de mettre fin à la Tempête et aux rumeurs sur le salut du tsarévitch Dmitri. L'église abritait de nombreuses icônes du tsarévitch décédé, et il était souvent commémoré. L'église a été construite aux frais de l'État sur ordre de Mikhaïl Fiodorovitch, qui a offert d'importantes terres à l'église. Cependant, l'église en bois a brûlé en 1703, comme de nombreux autres bâtiments de l'époque. Après la prise d'Azov par Pierre Ier, la construction navale sur la rivière Voronej a décliné, et la ville a été quittée par des spécialistes étrangers. Au début du XVIIIe siècle, de nombreux fonctionnaires, militaires et habitants des territoires d'Azov, transférés à l'ennemi, sont arrivés dans la ville, et ils avaient besoin d'églises. L'évêque Mitrophane a ordonné la construction d'une nouvelle église en pierre près de l'emplacement de l'ancienne église de Dimitri, la troisième à Voronej. En cinq ans, des fonds ont été collectés et des artisans ont été trouvés, et en 1720, la construction était achevée. Le nouveau temple a été consacré en l'honneur de Saint Nicolas, archevêque de Myre en Lycie.

En mai 1748, l'église a subi un grave incendie, mais a résisté, bien qu'elle ait perdu une grande partie de son intérieur. Le bâtiment a été réparé, ajoutant une chapelle en l'honneur du grand martyr Dimitri de Thessalonique, et plus tard, un clocher a été construit. En 1831, Voronej a souffert d'une épidémie de choléra, qui a emporté la vie d'un habitant sur six. L'épidémie a rapidement pris fin, et les habitants de la ville l'ont associée aux prières dans l'église de Nicolas devant l'icône de la Mère de Dieu de Tolga. Après cela, l'icône a été portée dans les rues de la ville, et les croyants ont été guéris. En l'honneur de cette icône, une nouvelle chapelle a été aménagée dans l'église. Depuis 1881, une administration paroissiale a fonctionné à l'église, bien que le clergé ait été petit : un prêtre, un diacre et un psalmiste. On sait qu'avant la révolution de 1917, le prêtre Fiodor Loukine y officiait. Les membres du clergé vivaient près de l'église dans des maisons paroissiales. Malgré leur petit nombre, le clergé a activement aidé pendant les guerres russo-japonaise et mondiale, en organisant des prières pour la victoire des armes russes et en collectant des dons pour l'armée et les familles des morts et des blessés.

À l'époque soviétique, le siège des évêques rénovateurs de Voronej se trouvait dans la cathédrale de l'Annonciation du monastère de Mitrophan, puis a été transféré à l'église de Nicolas. Les fidèles ont exigé le retour de l'église dans le giron de l'Église véritable. Bientôt, les bolcheviks se sont désillusionnés par le mouvement rénovateur, et l'église a été fermée, mais pas pour longtemps. Pendant la Grande Guerre patriotique, les portes de l'église de Nicolas se sont ouvertes en premier parmi les églises de Voronej pour les croyants en 1942. Après la libération de Voronej, les services religieux ont repris et n'ont pas cessé depuis mai 1943.