Tai pati seniausia Vilniaus bažnyčia, pirmą kartą rašytiniuose šaltiniuose paminėta Lietuvos krikšto metais – 1387-aisiais, įsteigta dar Gedimino laikais į Lietuvą pakviestiems Hazos sąjungos miesto amatininkams ir pirkliams. Tai liudija ir Vidurio Europos regionui tradicinis šv. vyskupo Mikalojaus Miriečio – keliautojų, pirklių, amatininkų, belaisvių, vaikų globėjo – titulas. Išmūryta ji 1382 – 1387 m. LDK vietininko Vilniuje J.Jaunio (Janulio) rūpesčiu ir lėšomis. Šį statybos laiką patvirtina archaiškos architektūrinės ankstyvosios gotikos bažnyčios formos. Bažnyčia minima dar 1387 – 1397 m. dokumentuose. Bažnyčia rekonstruota ir atnaujinta kelis kartus, todėl interjere (skliautuose, altoriuose) ryškios XVI a. pradžios vėlyvosios gotikos ir XVIII a. vidurio vėlyvojo baroko formos. 1514 m. yra išlikęs konsekravimo aktas, apie 1525 m. išmūryti nauji tinkliniai skliautai. Po 1749 m. gaisro apie 1750 m. ir vėliau padaryta daug pakeitimų: pristatytas rokoko stiliaus muzikos choras, padidinti šoniniai langai. 1812 m. Prancūzai smarkiai apnaikino bažnyčią. Po to pristatytas bokštas, bažnyčia apjuosta mūrine tvora. Pati bažnyčia pastatyta iš raudonų plytų, Pabaltijo gotikiniu stiliumi.

Bažnyčia trijų navų, yra trys altoriai. Po 1972 m. remonto darbų iš didžiojo altoriaus Šv. Mikalojaus paveikslas buvo perkeltas į kairįjį šoninį altorių. Centriniame altoriuje – kryžius, o tarp kolonų stovėjo keturios skulptoriaus Rapolo Jakimavičiaus statulos: Kristoforo, šv. Teresėlės, šv. Kliaros ir šv. Juozapo su Kūdikėliu. Dabar kairiajame altoriuje – Šv. Mikalojaus paveikslas. Tarp kolonų ankščiau stovėjo Šv. Pranciškaus Ksavero ir Šv. Ignoto Lojolos statulos. Dešiniajame altoriuje – Sopulingosios Dievo Motinos bareljefas. Ankščiau tarp kolonų stovėjo šv. Marijos Magdalietės ir šv. Teresėlės skulptūros. 1930 m. Vilniaus lietuvių pastangomis bažnyčioje pastatytas paminklas Vytauto Didžiojo 500 metų mirties sukakčiai paminėti. Skulptorius Rapolas Jakimavičius nukalė jį iš vario ir marmuro. 1936 m. paminklą aptvėrė tvorele su dviem kardais, primenančiais kardininkų atsiųstus prieš Žalgirio mūšį. Po karo atidengta paminklinė lenta klebonui Krištapui Čibirui, klebonavusiam nuo 1924 m. iki 1942 03 23 ir žuvusiam nuo bombos, bolševikams pirmą kartą bombarduojant Vilnių. Šalia paminklinė lenta 1918 m. vasario 16-osios akto signatarui, kita bažnyčios Geradariams broliamsVileišiams. 1959 m. bažnyčios šventoriuje buvo pastatyta Vilniaus globėjo šv. Kristupo skulptūra (autorius Antanas Kmieliauskas).

Lietuviškos pamaldos pradėtos laikyti nuo 1901 m. ir nuo to laiko niekad nebuvo nutrauktos. Per tą laikotarpį klebonavo: kun. Juozas Kukta (1901 – 1906 m.), kun. dr. Antanas Viskantas (1906 – 1911 m.), kun. Petras Kraujelis (1911 – 1912 m.), kun. Vladislovas Jezukevičius (1912 – 1924 m.), kun. Krištapas Čibiras (1924 – 1942 m.). Kartu su juo nuo 1936 m. dar buvo kunigai Vincentas Taškūnas, Edmundas Basys ir Kazimieras Pukėnas. Taip pat šiuose namuose gyveno ir arkivyskupas Mečislovas Reinys. Tarpukariu, lenkų okupacijos laikotarpiu, tai buvo vienintelė bažnyčia Vilniuje, kurioje buvo meldžiamasi ir sakomi pamokslai lietuvių kalba. Pokario metais uždarius Vilniaus arkikatedrą baziliką ir Šv. Mikalojaus parapijos namuose įsikūrus Vilniaus arkivyskupijos kurijai, ši bažnyčia faktiškai atliko prokatedros funkcijas. Prie bažnyčios buvo lietuvių kultūros židinys. Bažnyčios kieme buvo salė, kurioje vykdavo lietuvių organizuojami susirinkimai, paskaitos, vaidinimai, eglutės vaikams. Be to, šiuose namuose gyveno klebonas K.Čibiras, kunigai V. Taškūnas ir E. Basys, taip pat vienintelės lietuviškos mokyklos Vilniuje vedėjas B. Suduikis, kuris vienu metu dar ir vargoninkavo šioje bažnyčioje. Be to, čia vargoninkavo J. Sinius, prieš karą ir grįžęs iš Sibiro tremties. Čia buvo žurnalo "Vilniaus aušros" redakcija. 1987 m., minint Lietuvos krikšto jubiliejų, sovietų valdžios ištremtas ir persekiojamas vyskupas Julijonas Steponavičius iškilmingas Šv. Mišias celebravo būtent šioje bažnyčioje.

2000 m. klebono E. Paulionio rūpesčiu pradėti restauravimo darbai: sutvirtinti bažnyčios pamatai, čerpėmis perdengtas bažnyčios stogas, pakeisti langai, restauruoti bažnyčios skliautai. 2004 m. klebono Medardo Čeponio pastangomis restauruota presbiterija ir parapijos namai, 2008 m. atnaujintas centrinis altorius, o 2010 m. abu šoniniai altoriai. 2013 m. restauruota šventoriaus tvora.