Tai pati seniausia Vilniaus bažnyčia, pirmą kartą istoriniuose šaltiniuose paminėta 1320 m., kai Lietuvos didysis kunigaikštis Gediminas pakvietė krikščioniškosios Europos amatininkus ir pirklius atvykti į Vilnių. 1323 m. laiške pranciškonams jis rašė, kad Vilniuje jiems pastatyta bažnyčia. Tai, kad bažnyčia buvo susijusi su pirklių atvykimu į miestą, liudija jai suteiktas Vidurio Europos regiono tradicinis šv. vyskupo Mikalojaus Miriečio – keliautojų, pirklių, amatininkų, belaisvių, vaikų globėjo – titulas.

Bažnyčia buvo išmūryta 1382–1387 m. LDK vietininko Vilniuje J. Jaunio (Janulio) rūpesčiu ir lėšomis. Šį statybos laiką patvirtina archajiškos architektūrinės ankstyvosios gotikos bažnyčios formos. Bažnyčia rekonstruota ir atnaujinta kelis kartus, todėl išryškėja interjero (skliautų, altorių) XVI a. pradžios vėlyvosios gotikos ir XVIII a. vidurio vėlyvojo baroko formos.
Bažnyčią į tris navas dalija grakštūs stulpai, besiremiantys į žvaigždinius skliautus.  Didžiajame altoriuje – Nukryžiuotasis. Kairiajame altoriuje – šv. Mikalojaus paveikslas. Dešiniajame altoriuje gerbiamas išskaptuotas iš medžio, dažytas ir paauksuotomis plokštėmis uždengtas Sopulingosios Dievo Motinos paveikslas.

1901–1939 m. Šv. Mikalojaus bažnyčia buvo vienintelė Vilniaus bažnyčia, kurioje vyko lietuviškos pamaldos, todėl ji tapo žinoma kaip lietuvių kultūros židinys. 1930 m. Vilniaus lietuvių pastangomis bažnyčioje pastatytas paminklas Vytauto Didžiojo 500 metų mirties sukakčiai paminėti. Pokario metais, uždarius Vilniaus arkikatedrą baziliką, bažnyčia atliko prokatedros funkciją. 1959 m. šalia bažnyčios pastatyta skulptoriaus Antano Kmieliausko sukurta Vilniaus globėjo šv. Kristoforo skulptūra. Tai buvo savotiškas rezistencijos aktas, nes miesto herbą, kuriame vaizduojamas šis šventasis, sovietų režimas buvo uždraudęs.