Gemäss einer Urkunde bestand im Kahlenbergerdorf bereits um 1168 eine romanische Kirche, welche dem hl. Johannes dem Täufer geweiht war. Ab 1250 ging das Kirchenpatronat an das Stift Klosterneuburg über, und sechs Jahre später erhält die Kirche ihren ersten beglaubigten Pfarrer. Während der Ersten Türkenbelagerung um 1529 brannte die Kirche zum ersten Mal nieder, wurde jedoch wieder aufgebaut. Um 1633 wurde die Kirche mit einem barocken Kleid versehen, fiel bei der Zweiten Türkenbelagerung um 1683 jedoch erneut einem Brand zum Opfer. In den folgenden 80 Jahren entstand die barocke Ausstattung (Altäre, Kreuz), welche heute noch besteht. Ein dritter Brand im Jahre 1771 richtet abermals grossen Schaden an, welcher jedoch behoben wurde. Die Franzosenkriege bescherten der Kirche um 1809 weitere Schäden. Umfassende Renovierungen, Erweiterungen und Veränderungen wurden in den Jahren 1896, 1962 und 1993 vorgenommen. 1992 wurde ein Raum unter dem Kirchturm entdeckt, welcher offensichtlich als Karner genutzt wurde. Gefüllt mit menschlichen Knochen dürfte er nach der Auflassung des umliegenden Friedhofes als Sammelraum für die hier Bestatteten genutzt worden sein.

Die kleine Kirche im Kahlenbergerdorf steht inmitten der Siedlung fast schon versteckt und ist nur dank des auffallenden grünen Turmhelmes von Distanz her auszumachen. An der Aussenwand des Chorraumes sind barocke Grabsteine aus dem frühen 17. Jrh. eingelassen. Noch heute sind in der Kirche Zeugen aus alter Zeit zu sehen, so beispielsweise der achteckige frühgotische Taufstein aus rotem Marmor aus dem Jahre 1300 und das vergitterte Sakramentshäuschen. Die Bildsäule im Kirchhof stammt aus der Zeit um 1470.