Vznik kostela byl dlouhý proces. Když Žulová roku 1793 získala statut města, začala hospodářsky se rozvíjet jako středisko těžby kamene a sídlo správy. Dlouho si však nemohla dovolit vlastní duchovní službu. Zejména po uzavření poutní kaple na Boží hoře roku 1785 (v důsledku josefinských reforem) město opakovaně prosilo o povolení stavby nového kostela.

Rozhodujícím momentem se stalo odkázání 1100 zlatých mlynářem Franzem Meisel z Vápenné v roce 1800, který podmínil dar tím, aby se kostel postavil do deseti let. Roku 1798 město obdrželo svolení od vratislavského biskupa a zemských úřadů. Roku 1805 pak biskup věnoval pozemek - objekt bývalého hradu Frýdberk, který byl po třicetileté válce jen nejnutněji opraven a sloužil jako pivovar. Biskup poskytl i bezplatný stavební materiál. Stavební práce byly zahájeny 4. března 1809 a na podzim téhož roku ukončeny. Vysvěcení provedl 4. listopadu 1810 biskupský komisař Johann Rother.

Stavitelé využili existující mohutnou hradní věž a přistavěli k ní jednolodní budovu v jednoduchém klasicistním stylu s drobnou nástavbou zvonice. Kolem budovy v prostoru vymezeném starou hradní fortifikací umístili hřbitov. Roku 1813 byla u kostela zřízena duchovní správa (lokalie, od roku 1870 farnost).

Vybavování trvalo dlouho. Roku 1860 obdržel kostel nový zvon, roku 1863 hlavní oltářní obraz, roku 1875 hlavní oltář. Postupná sochařská a obrazová výzdoba byla instalována zejména v letech 1875 až 1900. Na počátku 20. století se začaly objevovat problémy - věž a zdi se hýbaly, zejména tam, kde se napojovaly na středověké zdivo bergfritu. Mezi roky 1903 a 1904 musela proběhnout zásadní renovace: vysoká špičatá střecha byla nahrazena nižší (aby se snížilo zatížení zdí), část zdiva byla nahrazena a nově ukotvena. V té době obdržel kostel novou výmalbu od malíře Aloise Bauche z Vidnavy. Roku 1920 dostal na věž hodinový stroj od firmy R. Thöndel, kolem roku 1923 vznikl další zachovaný zvon, roku 1932 byly namontovány nové varhany.

Dominantou stavby je válcová bergfritová věž z lomového kamene, která v dolní části měří průměr 11 metrů a stěny silné až 4 metry. Kostel se nachází severovýchodně od středu Žulové na ostrohu nad soutokem Stříbrného a Vápenného potoka. Přístup do areálu zajišťuje kamenný most z roku 1846.

Po druhé světové válce a odsunu německého obyvatelstva v letech 1945 až 1946 se Žulová jen zčásti znovu osídlila. Péče o kostel nebyla důsledná, ale v letech 1963 až 1964 prošel částečnou novou výmalbou a opravou původních maleb. Roku 1963 byl prohlášen za kulturní památku. Zásadnější opravy, zejména střechy, obdržel až po roce 1989 s finančním přispěním vysídlenců z Rakouska. Nové věžní hodiny byly instalovány a v roce 2010 opraveny varhany.