Kostel se nachází na severním konci města u státní silnice vedoucí do Polska. Dříve to bylo před Dolní bránou. Je vystavěn v barokním slohu s prvky tzv. slezského baroka.Na jeho místě stávala starší kaple, která byla postavena vedle městského špitálu zmiňovaného z roku 1552. Tuto kapli nechal postavit poštmistr a výběrčí daní Johann Georg Nentwig ze Zlatých Hor a je doložena z roku 1687. Vedle kaple byl v roce 1695 na ploše Dvorní zahrady založen nový hřbitov. Za prusko-rakouské války v letech 1740 - 1742 bylo město roku 1741 obsazeno pruským vojskem pod velením generála Schwerina a zapáleno. Shořelo na 300 domů i s touto kaplí.Nový kostel byl vybudován po skončení tzv. sedmileté války (1756 - 1763) v letech 1764 - 1768 a stál 2.347 tolarů a 33 grošů. Vysvětil jej 6. září 1772 biskup Philipp Gotthard Schaffgotsch. Kostel byl postaven z kamene a poprvé byl opravován v roce 1888. Roku 1857 a později i v roce 1906 byla kostelu vyměněna věžní hlavice.V roce 1864 byla ke kostelu směrem k městu přistavěna budova, která sloužila jako městská nemocnice a částečně jako útulek pro místní staré občany. Za děkana V. Braunera byl z farního kostela Nanebevzetí P. Marie přenesen do kostela sv. Kříže oltář, který byl vyroben Raimundem a Rafaelem Kutzerem z Horního Údolí.V roce 1738 byl naproti kostela přes cestu postaven chudobinec, který byl v roce 1899 zmodernizován. O provoz nemocnice, chudobince i kostela pečovaly až do roku 1945 řeholní sestry z řádu boromejek.V letech 1997 až 1999 uskutečnil farář M. Michna generální rekonstrukci exteriéru. Byl opraven krov, střecha, fasáda a vstupní dveře. Opravu financoval stát, římsko-katolická církev i město Zlaté Hory. V roce 2000 se započalo s opravou interiéru.