Kirchlich gehörte Baden durch Jahrhunderte zur Diözese Passau. An diese lange Verbundenheit erinnert, dass die Pfarrkirche von Baden dem Hl. Stephanus geweiht ist, dem Patron von Passau. Ursprünglich war Baden eine Filiale der Mutterpfarre Traiskirchen.
Im Jahre 1220 wird erstmals urkundlich ein Priester in Baden erwähnt. Welche Stellung er hatte - er könnte Kaplan an der Burg Baden gewesen sein - wird nicht erwähnt. Als Traiskirchen mit all seinen Filialen dem Stift Melk unterstellt wird, kommt es 1312 zur Loslösung von Baden. Es wird nun selbstständige Pfarre unter dem Patronat von Melk. Nach länger anhaltenden Streitigkeiten zwischen den Bischöfen von Passau und dem Stift Melk tritt 1693 das Stift das Patronatsrecht an Passau ab. Als die 1469 gegründete Zwergdiözese Wien zum Erzbistum erhoben wird, kommt es 1729 zur Abtretung des bisher zu Passau gehörenden Gebietes südlich von Wien, darunter auch Baden. 1784 wird Baden schließlich landesfürstliche Pfarre.
Aus dem ursprünglichen Pfarrgebiet von Baden sind mehrere neue Pfarren entstanden: Sooß (ab 1783 Pfarre), St. Christoph (1783 als St. Helena zur Pfarre erhoben) und St. Josef (1990 zur Pfarre erhoben).

REKTORATSKIRCHE "FRAUENKIRCHE"

Kirche in der Frauengasse zwischen Hauptplatz und Josefsplatz gelegen.