Dějiny kostela sahají pravděpodobně do 13. století. Byl vybudován jako trojlodní stavba v raně gotickém slohu a postupně byly prováděny další přístavby. V rámci rekatolizace byl kostel přestavěn do monumentální barokní podoby. Gotickou podobu kostela však dodnes připomíná stará sakristie, středověká věž představená před presbyterium a půdorys kostela.
Největší změny budova doznala
po velkém požáru v červenci roku 1699, kdy shořela střecha, 5 oltářů, varhany a žár byl natolik silný, že
roztavil i kostelní zvon. Poté byl
kostel přestavěn v barokním slohu. Další požár postihl kostel v březnu 1833, kdy vyhořel hlavní oltář. Práce na novém oltářo provedl řezbář Bernard Kutzer z Horního Údolí. Přes dva metry vysoké postavy sv. Gregora, sv. Ambrosia, sv. Augustina, sv. Hieronyma, sv. Valentina a sv. Achacia jsou také vynikající díla tohoto mistra. V roce 1900 byl kostel vyzdoben nástěnnými malbami. V noci ze 17. na 18. července 1870
udeřil do oltáře a zadní věže kostela blesk. Některé části oltáře byly poškozeny a ohořel rám mariánského obrazu. O deset let později udeřil blesk znovu a poškodil západní stěnu kostela a ciferník hodin. Děkan Vincenc Brauner nechal v kostele v roce 1912 položit barevnou dlažbu z umělého mramoru a zavedl elektrické osvětlení. Poslední generální oprava zde proběhla roku 1976.
V okolí kostela jsou dodnes vidět
zbytky starého hřbitova. Na východní zdi je ještě dnes umístěná nejstarší náhrobní deska datována k 7. srpnu 1649. Jedná se o náhrobní desku Johanna Zottmantla, starosty
Zlatých Hor.