Įvairių autorių nurodytos skirtingos šios cerkvės pastatymo datos. Juozapas Ignotas Kraševskis teigė, kad cerkvė pastatyta, valdant LDK didžiajam kunigaikščiui Algirdui apie 1345–1377 metus. V.Vinogradovas taip pat įrodinėjo, jog ši cerkvė statyta didžiojo kunigaikščio Algirdo laikais jo antrosios žmonos Julijonos iniciatyva. F.Dobrianskis teigė, kad cerkvė turėjo stovėti jau Gedimino laikais apie 1322–1340 metus.[1]
Pirmoji cerkvė pastatyta medinė. Cerkvei sudegus, mūrinę atstatė LDK etmonas, kunigaikštis Konstantinas Ostrogiškis, laimėjęs Oršos mūšį, gavęs karaliaus Žygimanto I leidimą pastatyti dvi cerkves. Užuot statęs naujas, jis nusprendė suremontuoti dvi senas, apgriuvusias cerkves: šią ir Švč. Trejybės. Cerkvė buvo perstatyta gotikos stiliumi.[1][2][3][4][5]
Po Brastos unijos 1609 m. Zigmantas Vaza cerkvę, kaip ir visas kitas LDK cerkves, paskyrė unitams. Cerkvė buvo tvarkoma pasaulietinio klero kaip parapijos bažnyčia. Tuo skyrėsi nuo kitų Vilniaus cerkvių.[2]
XVIII a. viduryje ji kelis kartus stipriai degė, po gaisrų atnaujinta vėlyvojo baroko stiliumi. Buvo paaukštintas cerkvės bokštas. 1827 m. cerkvė iš unitų (paskutinis unitų klebonas joje buvo Vilniaus universiteto profesorius slavistas Michalas Bobrovskis) grąžinta stačiatikiams, suremontuota ir pašventinta 1845 metais.[2][4]
1865 m. Michailo Muravjovo pastangomis pradėta cerkvės rekonstrukcija. Nugriauti priešais stovėję namai, atidengtas cerkvės fasadas. Pati cerkvė rekonstruota pagal Aleksandro Rezanovo projektą. Jos rekonstrukciją atliko architektas Nikolajus Čaginas. Šios rekonstrukcijos metu pastatyta Arkangelo Mykolo koplyčia. Restauratorių duomenimis, šios rekonstrukcijos metu sunaikinta cerkvės viduje buvusi polichromija. 1869 m. cerkvės rekonstrukcija buvo baigta ir ji įgijo dabartinę išvaizdą.[1][2]
1875 m. Šv. Mikalojaus parapijos klebonu buvo Joanas Šverubovičius. Tais metais jam gimė sūnus, iš kurio išaugo pagarsėjęs rusų aktorius Vasilijus Kačialovas. XX a. pirmoje pusėje cerkvės diakonu dirbo lietuvių aktoriaus Leonido Muraškos tėvas Adomas Muraška. Šią cerkvę lankė Levas Karsavinas.[2]
TSRS valdžia parapiją užregistravo 1947 metais, 1961 m. jai priklausė 800 tikinčiųjų. 1949 ir 1956 m. cerkvė remontuota.
Cerkvės vidus
Cerkvės viduje – elegantiškų arkų laikomas barokinis XVIII a. antros pusės skliautas, spėjama, suprojektuotas Jono Kristupo Glaubico, ir spalvoto stiklo langų vitražai, kurių yra penki. Jie padaryto iš plono bespalvio ir spalvoto stiklo, sujungto švinu.[2][3]
Cerkvės ikonostasas sukurtas neobizantine maniera, jis trijų aukštų, medinis. Dauguma jo ikonų iš XIX amžiaus. Ikonose tradicinis auksinis fonas, suderintas su figūrų tapyba. Dešinėje altoriaus kabo paveikslas, kuriame vaizduojamas Šv. Mikalojus. Kitoje altoriaus pusėje pastatyta didelė ikona, vaizduojanti šv. Panteleimoną, gydytojų globėją. Ant šoninių cerkvės sienų kabančiose ikonose vaizduojama Vilniaus istorija. Atskirai stovinčiame kijote yra Rusijos globėjų Romanovų atvaizdas. Cerkvėje taip pat kabo Aušros vartų Dievo motinos paveikslas.[2][4]
Koplyčią dengia aštuoniakampis kupolas, kurį supa bokštelių pavidalo kolonėlės. Virš koplyčios portalo įrašyti žodžiai iš pranašo Danilo apie Šv. Mykolą Arkangelą. Abipus koplyčios įmūrytos atminimo lentos. Kairėje lentoje parašyta, kad koplyčia pastatyta 1865 m. Koplyčia pašventinta 1869 metais.[3][4]