Projekt výstavby kostela vytvořil architekt Jan Blažej Santini - Aichel (1677 - 1723) mezi koncem dubna a začátkem srpna 1719. Zadavatelem stavby kostela byl opat žďárského kláštera Václav Vejmluva (1670 - 1738). Realizace projektu započala již 13. srpna 1719. Původní Santiniho dochované plány kostela se od realizace poněkud liší. Základní kámen byl vysvěcen již v rozestavěné stavbě 16. května 1720. V roce 1721 byl blahořečen Jan Nepomucký a žďárský opat Václav Vejmluva získal vzácnou relikvii - kůstku, k níž byl přirostlý mučedníkův jazyk. S tím souvisí i změna výzdoby klenby, kde měla být dle původních plánů Santiniho pouze deseticípá hvězda, k níž přibyla plastika jazyka v plamenech. V témže roce byla provedena hrubá stavba kostela a v roce 1722 byla stavba dokončena. Kostel byl vysvěcen olomouckým biskupem 27. září 1722, pouhý týden po dokončení zednických prací.
Výzdoba interiérů kostela pokračovala ještě dlouho po vysvěcení. Hlavní oltář byl realizován podle Santiniho návrhu v letech 1725 - 1727. Základy ambitů byly zřejmě vybudovány již v roce 1719. Byly zasypány a později odkryty až před výstavbou obvodové zdi. K té byly postupně dostavovány ambity s bránami a kaplemi. Roku 1729 byly již dvě z kaplí zastřešeny, v roce 1731 už chyběla střecha jen na poslední - páté. S výstavbou ambitů se začalo až několik let po dostavbě kostela. K jejich částečnému dokončení došlo v roce 1735. Ambity byly dokončeny zřejmě až v roce 1769. Vybavení všech pěti kaplí v ambitech bylo po požáru v roce 1784 odvezeno. Pozůstatky vybavení lze dnes vidět v tzv. Německé kapli, kde se dochovaly i původní malby ambitů.
V roce 1974 byl kostel zapsán do seznamu světově výjimečných staveb UNESCO. Tehdy se začalo s rozsáhlými obnovovacími pracemi, které byly ukončeny až v roce 1982. V prosinci roku 1994 byl kostel zapsán do Seznamu světového dědictví UNESCO.
Okolí kostela bylo původně holé, v polovině 19. století byla Zelená hora zalesněna. Odlesnění okolí kostela začalo v roce 2006, dnes je již okolí kostela v původním stavu.