Erste urkundliche Erwähnung 1094. Anstelle älterer - offensichtlich sehr groß dimensionierter - Kirchenbauten (vom spätromanischen Bau des 13. Jahrhunderts hat sich die zwischen Chor und Schiff gelegene Halle erhalten) wurde im 14. Jahrhundert ein frühgotisches, dreischiffiges Langhaus (Basilika) errichtet. Der hohe gotische Chor mit Netzrippengewölbe, fünf hängenden Schlusssteinen sowie figuralen Konsolen stammt aus der 1. Hälfte des 15. Jahrhunderts.
Vermutlich im 16. Jahrhundert wurde die Pfarrkirche befestigt (Tabor) und bildete so während der Zeit der Türkenkriege für die Bürger eine sichere Zuflucht. Seit 1548 hatten die Freiherren und späteren Grafen Hoyos die Vogtei über die Pfarrkirche. Die bemerkenswerte Rokokoeinrichtung der Kirche geht auf die Familie Hoyos zurück.
1630/31 stiftete Hans Balthasar von Hoyos in Neunkirchen ein Minoritenkloster, dem die Pfarre inkorpiert wurde. Seit dieser Zeit ist die Pfarrkirche zugleich auch Klosterkirche. Nach dem Kirchenbrand im Jahre 1907 romantisierende bauliche Veränderungen an der Außenseite des Chors sowie am Kirchturm.