Die Weidlinger verdanken ihre erste Kirche dem reichen Klosterneuburger Bürger Andreas Lohner. Er ließ von 1403 – 1407 auf eigene Kosten auf Weidlinger Boden eine Kapelle zu Ehren des hl. Petrus und der hl. Katharina erbauen. Mitstifter und erster Seelsorger war Hermann von Pillichdorf. Er las wöchentlich vier Messen für die Weinhauer, aber nicht am Sonntag, um der Stiftspfarre, zu der Weidling gehörte, keinen Abbruch zu tun. Die heilige Katharina hat man später aus bisher unbekanntem Grund vergessen. 1614 wir an ihrer Stelle schon der hl. Paulus erwähnt.
Leider gibt es keine Pläne über das Aussehen der ersten Kapelle. Sicher ist, dass sie nur jenen Teil umfasste, der sich bis heute als gotisch präsentiert. Ein Langhaus mit 3/8 Chorabschluss und Kreuzrippengewölbe auf Konsolen. Mit Sicherheit kann auch angenommen werden, dass das erste Gotteshaus noch keinen Turm hatte. 1614 dürfte es aber dann schon einen Turm gegeben haben. Die Türken zogen 1683 über Weidling nach Klosterneuburg. Dabei wurde der Ort schwer verwüstet und viele Bewohner fanden den Tod. Im Zuge des Wiederaufbaues wurde auch die Kirche vergrößert. 1686 wurden an die bestehende Kirche zwei Joche auf die heutige Länge angefügt.
Der barocke Erweiterungsbau ist durch seine gänzlich andere Bauart zur alten Kirche leicht zu erkennen. 1717 dürfte auch der alte Turm baufällig gewesen sein, und so wurde er durch einen neuen ersetzt. Eine neue Sakristei wurde gebaut, die alte dient heute als Beichtkapelle. Es entstand nun auch die neue Kanzel, deren Aufgang einen Teil der alten Sakristei in Anspruch nahm.
1783 wurde Weidling im Zuge der josefinischen Pfarrregulierung selbständige Pfarre. Den heutigen reizvollen Zwiebelhelm des Turmes, der noch ganz barocke Formen aufweist, entstand 1831; geplant vom Stifts- und Stadtbaumeister Ignaz Decherbauer. 1851 kam dann die neue Orgel mit zwölf vollen Registern und zwei Verbindungszügen vom Klosterneuburger Orgelbauer Franz Reusch dazu. Über 80 Jahre war diese Orgel im Dienst der Weidlinger Pfarrkirche. 1931 gab sie ihren Geist auf und wurde durch eine pneumatische Orgel der Firma Panhuber ersetzt.
Im Jahr 1887 erhielt die Kirche einen neuen Kreuzweg und 1889 erfolgte die große Innenrenovierung mit der Errichtung von neugotischen Altären, neuen Statuen von Petrus und Paulus und neuen Glasfenster, welche die hl. Maria und den hl. Leopold darstellten. Nach dem II. Vatikanischen Konzil 1964 wurde der Altarraum neuerlich umgestaltet, indem die Neugotik aus der Kirche wieder verschwand. Auch die beiden neugotischen Fenster wurden durch moderne ersetzt, die der Weidlinger Künstler Amadeus Dier 1956 entwarf. 1970 wurden Ambo, Weihwasserbecken und der neue Volksaltar in moderner, schlichter Art in den alten gotischen Chor eingefügt. Die nächste große Innen- und Außenrenovierung der Kirche erfolgte in den Jahren 1980 bis 1984.
Nicht einmal 70 Jahre tat die Panhuber-Orgel ihren Dienst. So kam es 1996 zur Gründung des Orgelvereines, mit dem Ziel zur Neuanschaffung eines romantisch klingenden Instruments. Der Orgelbauer Eisenbarth aus Passau errichtete schon bald eine neue mechanische Orgel, die zu Pfingsten 1999 ihrer Bestimmung übergeben wurde.
Die letzte umfangreiche Innenrenovierung der Kirche erfolgte im Jahre 2012 und umfasste unter anderem den Einbau einer Fußboden- und Wandheizung, die Erneuerung von Verputz, Malerei, elektrische Anlagen und Beleuchtung, die Montage einer Lautsprecheranlage, ein Generalservice mit Hauptstimmung der Orgel, sowie die Neugestaltung des gesamten Altarraumes.
Pfarrkanzlei Weidling im Jahre 2013
