Bereits am 29. März 1148 wird in Judenburg eine romanische Kirche urkundlich erwähnt. Leider sind keine Reste dieses Baus gesichert, aber Umbauten sind überliefert.
Nach einem Stadtbrand am 9. August 1504 kam es zu einem großzügigen spätgotischen Neubau, welcher wahrscheinlich in Form einer dreischiffigen Hallenkirche ausgeführt wurde.
Zur selben Zeit entstand der direkt neben der Kirche stehende Stadtturm, welcher zugleich Glockenträger und Feuerwachstube war und dessen Besitz sich noch heute Stadt und Pfarre teilen.
Am 5. Juni 1670 zerstörte abermals ein Stadtbrand den spätgotischen Bau und es kam zu einem barocken Neubau unter Einbeziehung verbliebener Bausubstanz. Ein neuerlicher Stadtbrand 1709 verzögerte die Fertigstellung, zerstörte das neue Dach und beschädigte die Einrichtung.
Im Laufe des 18. Jahrhunderts wurde die Kirche endgültig fertiggestellt und erhielt schöne spätbarocke Einrichtungsgegenstände und Kunstwerke.
Zwischen 1899 und 1902 kam es noch einmal zu Bautätigkeiten an der Fassade, welche durch weiter Stadtbrände 1807 und 1840 in Mitleidenschaft gezogen war. Im Stile des Historismus wurde das Aussehen dem oberitalienischen und römischen Barock nachempfunden.
