Původně romanský kostel, postavený na skalnatém ostrohu proti Znojemskému hradu, byl zasvěcen sv. Mikuláši, patronu kupců, a to nejspíš díky osadě obchodníků, která vznikla v okolí kostela. Nejstarší zmínkou o kostele, je jeho vyobrazení na denárech ražených ve Znojmě za knížete Lutolda, kolem roku 1100.
Při obrovských požárech města v první třetině 14. století vzal starý kostelík za své, takže loucká vrchnost musela přikročit ke stavbě zcela nového chrámu, který byl založen roku 1338. Trojlodní chrám o celkových rozměrech 60 x 22 m, byl natolik významný, že v něm, v prosinci roku 1437, bylo veřejně vystaveno mrtvé tělo císaře Zikmunda Lucemburského. K kostele se prolínají vlivy gotiky i baroka – interiér byl totiž v baroku upravován.
Trojlodí i presbytář jsou zaklenuty síťovou žebrovou klenbou ovlivněnou činností Petra Parléře. V kněžišti můžete obdivovat unikátní gotické fresky s pašijovými náměty i krásná gotická plastika bičovaného Krista u kůlu. Za zmínku stojí také zajímavá barokní kazatelna v podobě zeměkoule, od J. Winterhaldera z roku 1760, a nádherné novogotické varhany na kúru. Věž kostela patří k nejmladším částem budovy, neboť vznikla teprve v polovině 19. století. Byla ke kostelu přistavena netradičně na jeho východní stranu. Původní věž kostela stála na jižní straně, v místech dnešní malé vížky.
Ke kostelu se dostanete ulicí Velká Mikulášská, která vede z Masarykova náměstí v centru města. Z prostranství před kostelem je nádherný výhled na údolí řeky Dyje, znojemskou přehradu, rotundu sv. Kateřiny a část Znojemského hradu.