Pirmā baznīca celta 13. gadsimtā. Tā veltīta zvejnieku un jūrnieku aizstāvim Sv. Nikolajam. Pārbūvēta no 1405. līdz 1420. gadam. 1515. gadā tika pārbūvēts tornis. Nikolaja baznīca bija vienīgā Tallinā, kura necieta svētbilžu grautiņu laikā, jo baznīcas durvis esot bijušas aizlodētas. 16. gadsimtā baznīcu piešķīra luterāņiem. 17. gadsimtā beigās torni vēlreiz pārbūvēja baroka stilā, tas ieguva mūsdienu siluetu. Baznīca smagi cieta padomju aviācijas Tallinas bombardēšanā 1944. gada 9. martā. Pēc Otrā pasaules kara baznīcas smaili atjaunoja, tomēr 1982. gada 13. oktobrī ugunsgrēkā smaile atkal nogāzās. 1984. gadā šeit tika atklāts muzejs un koncertzāle. No muzeja eksponātiem īpaši vērtīga ir 1633. gada Bernta NotkesDanse Macabre.