Das Dorf Weidling jenseits des Kahlenberges erhielt in den Jahren 1403 bis 1407 eine turmlose gotische Kapelle, welche den Heiligen Petrus und Katharina geweiht war und von einem reichen Klosterneuburger Bürger namens Andreas Lohner finanziert wurde. Ab 1614 wird der Heilige Paulus anstelle der Katharina als zweiter Kirchenpatron erwähnt. Zu dieser Zeit dürfte die Kapelle bereits erweitert worden sein und einen Turm besessen haben. Nachdem im Jahre 1683 die Türken ihre Spuren der Verwüstung auch in Weidling hinterlassen hatten, wurde die stark zerstörte Kirche wieder aufgebaut und gleichzeitig erweitert. Sie erhielt zwei Joche, wodurch sie die heutige Länge erreichte, und wurde im barocken Stil ausgestattet. Um 1717 wurde der baufällig gewordene Turm durch einen neuen barocken Glockenturm ersetzt, und eine neue Sakristei wurde angebaut.

Im Rahmen der Reformationen Josefs II. wurde Weidling im Jahre 1783 zur selbständigen Pfarre erhoben. Um 1831 wurde von Ignaz Decherbauer der heutige Glockenturm errichtet, welcher stilistisch ganz der längst verklungenen Barockzeit angepasst ist. Um 1851 wurde eine Orgel installiert, welche um 1931 durch eine neue ersetzt wurde. Umfassende Erneuerungen wurden im Jahre 1889 im Inneren der Kirche vorgenommen, indem man die barocken Altäre durch neugotische ersetze, neue Statuen der Kirchenpatrone Peter und Paul aufstellte und neue Glasfenster installierte. 1964 nahm man erneut Änderungen im Inneren vor, die neugotischen Altäre wurden wieder entfernt und die neugotischen Fenster durch modern bemalte Glasfenster eines einheimischen Künstlers ersetzt. Volksaltar, Ambo und Taufbecken sind zwar modern und schlicht, lassen aber dadurch den alten gotischen Chor umso mehr zur Geltung kommen.