Die Baugeschichte unserer Pfarrkirche vor dem Neubau am Ende des 15. Jahrhunderts läßt sich nur anhand der noch vorhandenen Bauteile vermuten. Urkundlich erwähnt ist lediglich die Existenz eines Karners (Beinhaus) im Jahre 1258. Da aber schon vor dieser Zeit Priester in Baden gewirkt haben und die Burg Baden sicherlich über eine Kirche oder Kapelle verfügte, kann man annehmen, daß bereits gegen Ende des 12. Jahrunderts sich auf dem heutigen Platz ein Kirchenbau befand.
Der unmittelbare Vorgängerbau stammt aus der Romanik. Diese Kirche war vermutlich ein dreischiffiger Bau mit zwei niedrigen Türmen zwischen denen sich der Altarraum und die Apsis befanden. Um 1400 wurde mit dem Bau eines gotischen Presbyteriums samt Unterkirche begonnen, das über der romanischen Apsis erbaut wurde und diese schließlich ersetzte. Das Langhaus der Kirche wurde in der zweiten Hälfte des 15. Jahhunderts errichtet, und zwar unter Einbeziehung der romanischen Außenmauern. In diese Zeit fällt auch die Errichtung des Hauptturmes über den beiden bestehenden romanischen Türmen. Diese Arbeiten - vermutlich durch eine teilweise Zerstörung der Kirche während der Ungarnkriege notwendig geworden - mußten in diesen unruhigen Zeiten immer wieder unterbrochen werden. Der Hauptturm schließlich wurde nicht vollendet und nur mit einem Satteldach bedeckt. Erst im Jahre 1697,  nachdem der Turm in den Türkenkriegen beschädigt wurde, setzte man den heute so typischen barocken Zwiebelhelm auf. Die am nördlichen Vorturm noch vorhandenen Reste einer "Mordgalerie" erinnern an die Einbeziehung der Kirche in die Verteidigungsanlagen der Stadt. Um das Jahr 1480 soll die Gotisierung abgeschlossen gewesen sein. Rätsel gibt uns der im Westen über dem Hauptportal befindliche Turm auf. Der sogenannte "abgeschossene Turm" ragte einst weit über das Dach hinaus und wurde, wie der Hauptturm, in den Türkenkriegen schwer beschädigt. Erst 1827 erhielt er sein heutiges Aussehen. Man nimmt an, daß auch dieser Turm aus der Zeit der Gotik stammt.
Im 67 Meter hohen Turm befindet sich übrigens die sogenannte Paramentenkammer und die Türmerwohnung, in der noch bis ins 20. Jahrhundert der Mesner gewohnt hat. Die Glockenstube birgt fünf Glocken. Von ihnen überdauerten zwei die Weltkriege: die "Große Glocke" (2000 kg, Ton: H) aus dem Jahr 1832 und die "Litaneiglocke" (950 kg, Ton: e) von 1764. Die drei anderen Glocken wurden 1949 gegossen: die "Marienglocke", die "Josefsglocke" und die "Urbaniglocke".