In einer Urkunde von 1192 wird bereits eine Kirche in Kaiserebersdorf erwähnt, welche dem hl. Petrus geweiht war. Der hl. Paulus kam erst um 1399 als zweiter Kirchenpatron dazu. Im Laufe der Jahrhunderte erlitt die Kirche immer wieder Schäden durch Kriegseinwirkung oder Hochwasser von der nahe gelegenen Donau. Während der Türkenbelagerung von 1683 wurde die Kirche durch ein Feuer zerstört und musste neu aufgebaut werden, womit man im Jahre 1692 begann. In dieser Zeit hing am Weg nach Mannswörth an einem Baum ein Marienbildnis, bei dem sich wunderbare Dinge ereignet haben sollen, weshalb man im November dieses Bildnis samt Baum in die Kirche von Ebersdorf brachte. In der Folge erfuhr das Gotteshaus einen immensen Zustrom an Pilgern, was innert Kürze eine Erweiterung der Kirche erforderte. Mit dieser Aufgabe wurde der Baumeister Matthias Gerl beauftragt. Seither erscheint die Kaiserebersdorfer Pfarrkirche in ihrer heutigen Gestalt.

Die Pfarrkirche von Kaiserebersdorf steht am Münnichplatz an der Stadtgrenze Wiens. Das vielverehrte Wallfahrtsbild „Maria am Baum“ ist über dem Tabernakel in einem goldenen Strahlenkranz angebracht. Darüber ragt symbolisch der Baum empor. Links und rechts neben dem Marienbild stehen die Statuen der beiden Kirchenpatrone Peter und Paul. Die beiden Seitenaltäre und die Kanzel sind die weiteren zentralen Elemente der schmucken spätbarocken Ausstattung der Kirche. An den Seitenwänden des Kirchenschiffes stehen je an einem Wandpfeiler die Figuren der beiden Heiligen Johannes Nepomuk und Nikolaus. Im Zuge einer Innenrenovierung in den Jahren 2002/03 erhielt die Kirche einen eigenwlligen modernen Volksaltar und Ambo.