Impozantní trojlodní stavba v barokním slohu se při pohledu od Jeseníku vypíná se svými třemi věžemi nad historickým jádrem města.Dějiny kostela sahají pravděpodobně do 60. let 13. století. První nepřímé zmínky o něm jsou z roku 1339 a opět z roku 1376 - 1377. Byl vybudován jako trojlodní stavba v raně gotickém slohu a postupně byly prováděny další přístavby. Po roce 1467 byl opevněn jako náhrada za zničení hradu Edelštejna. Z roku 1477 je zaznamenáno jméno prvního faráře: Johann Molitor (česky Mlynář). Nejstarší vizitační zprávy z konce 16. století píší, že kostel byl zasvěcen Panně Marii a sv. Valentinovi.Největší změny zaznamenala budova po požáru města 17. 7. 1699. Shořela střecha, 5 oltářů a varhany. Zvon byl požárem roztaven a kronika zaznamenává, že shořel i 400 let starý dřevěný krucifix. Poté byl kostel přestavěn v barokním slohu. Hrubá stavba byla dokončena ještě za faráře Balthasara Chrisostoma Hauschilda ( 1672-1702). Jeho nástupce Johann Anton Hoppe opravu v roce 1708 dokončil a vysvětil. Roku 1740 byla na severní straně presbytáře vystavěna J.I. Töpperem z Prudniku nová sakristie s oratoří. Nově opravený a vnitřně vybavený kostel byl roku 1748 vysvěcem vratislavským biskupem Philipem Gotthardem Schaffgotschem. Další stavební úpravou v historii kostela byla v roce 1780 stavba kruhovité kaple sv. Josefa na jižní straně boční lodi . Stavbu financoval svobodný pán a rodák z Jarnoltowka, Joseph von Peretzki. V kapli byl také pohřben. V roce 1945 dal farář Gerhard Schubert ostatky Josepha von Peretzkého vyzvednout a uložit do nového sarkofágu.
V okolí kostela jsou dodnes vidět zbytky starého hřbitova, který byl zrušen farářem Philippem Steinem roku 1813. Na východní zdi je ještě dnes umístěná nejstarší náhrobní deska datována 7. srpna 1649. Jedná se o náhrobní desku Johanna Zottmantla, starosty Zlatých Hor. Z kroniky se pro zajímavost můžeme dovědět, že roku 1717 byla z kostela ukradena monstrance, nejlepší ornáty, kalich a další věci. Zloděj nebyl vypátrán.
21. března 1833 vyhořel hlavní oltář, ale již 4. října byl děkanem Philippem Dittrichem postaven v barokním slohu oltář nový. Řezbářské práce byly provedeny známým řezbářem Bernardem Kutzerem z Horního Údolí. Přes dva metry vysoké postavy sv. Gregora, sv. Ambrosia, sv. Augustina, sv. Hieronyma, sv. Valentina a sv. Achacia jsou rovněž vynikající díla tohoto mistra. V roce 1900 byl za děkana Gregora Kunze kostel vyzdoben nástěnnými malbami. Ty jsou dílem známých malířů Franze Templera a Emila Brendela ze Zlatých Hor.V noci ze 17. na 18. července 1870 udeřil při povodni blesk do zadní věže kostela a hlavního oltáře. Některé části oltáře byly poškozeny a ohořel rám mariánského obrazu. I5. srpna 1880 odpoledne udeřil blesk znovu a poškodil západní stěnu kostela a ciferník hodin.Roku 1896 byly v kostele instalovány nové varhany vyrobené firmou Rieger - Kloss z Krnova.Děkan Vincenc Brauner nechal v kostele v roce 1912 položit barevnou dlažbu z umělého mramoru a pořídit nové lavice. Dal postavit nové boční oltáře a zavedl elektrické osvětlení. V roce 1937 byly postaveny podle návrhů stavitele Josefa Dittricha předsíně před západním a severním průčelím kostela. Farář Gerhard Schubert (1941 - 1946) nechal umístit do kaple sv. Josefa obraz sv. Rocha, jehož autorem je opět Emil Brendel.V roce 1974 - 1976 byla za faráře Josefa Holka provedena generální oprava kostela. Byla natřena plechová střecha a zhotovena nová omítka. V listopadu roku 1999 byl proveden stavebně historický průzkum stavby a v roce 2001 započala postupná celková oprava kostela. Byla demontována celá báň východní věže, usazena nová konstrukce a pokryta měděným plechem. Na špici se již nyní skví i nová zlacená makovice.