Vermutlich zur Zeit der Besiedelung um das Jahr 1100 dürfte eine erste Kapelle in Heiligenkreuz vorhanden gewesen sein, urkundlich erwähnt wird „sacrum crux“ im Jahre 1265 und die Pfarrgründung erfolgte 1269.
Mitte des 16. Jahrhunderts wurde die ursprünglich gotische Kirche fertiggestellt, worauf der Schlussstein im alten gotischen Chor, der heutigen Marienkapelle, mit der Jahreszahl 1547 hindeutet.
Der viergeschossige Turm erhielt 1746 sein heutiges Aussehen und 1891 begann der große Neubau im Stil der Neorenaissance.
Im Innenraum findet man typisch barocke Einrichtungsgegenstände, wovon besonders der Hochaltar aus der Mitte des 17. Jahrhunderts besonders hervorsticht. Er stammt ursprünglich aus der Domkirche in Marburg an der Drau.
