Noch im 15. Jh. gehörte Leopoldau zur Pfarre Stadlau. Die Pfarrkirche dort fiel jedoch immer wieder verheerenden Hochwassern anheim, weshalb man in Kagran eine weitere Kirche baute. Doch auch diese war für die Leopoldauer immer wieder unerreichbar, weil die Donau das Land oft flutete. Deshalb ersuchte man in Leopoldau, dass die bestehende Kapelle zur Pfarrkirche erhoben wird. Die Erzdiözese Passau erteilte 1489 die Erlaubnis, und die Kapelle wurde unter dem Patrozinium Maria im Elend geweiht. Aber auch das Bestehen der Kapelle sollte unter keinem guten Stern stehen, denn auch in Leopoldau richtete die über die Ufer tretende Donau immer wieder grossen Schaden an. Die Kapelle wurde mit der Zeit stark in Mitleidenschaft gezogen, und als die erste Türkenbelagerung Wiens um 1529 erfolgte, wurde sie bis auf die Grundmauern zerstört.

Um 1696 begann man unter Probst Christoph II. den Bau der barocken Pfarrkirche in der heutigen Gestalt und mit der heutigen Ausstattung bis auf die Kirchbänke. Diese mussten während des Franzosenkrieges als Brennholz herhalten. Im Kirchenschiff wurde in der Zeit Fleisch zerlegt. Nach Ende des Krieges wurde die Kirche wieder als solche in Betrieb genommen, die jetzige Orgel installiert und neue Bänke angeschafft. Um 1876 erhielt die Kirche zusätzliche Ausstattungselemente. Eduard Swoboda bemalte die Wände des Chorraumes mit Engelgruppen. Weitere Malarbeiten erfolgten um 1897 durch Josef Kott. Kurz darauf wurden der Tabernakel und darunter das Antependium angebracht. Aus St. Michael zu Heiligenstadt wurden mehrere Figuren zur weiteren Ausschmückung hergeschafft, darunter auch der Hochaltar von Matthias Steinl. Die Muttergottes-Statue links vom Übergang zur Apsis stammt aus der ersten Hälfte des 14. Jh. und ist ein besonders wertvolles Objekt.

Dank weitgehender Verschonung im Zweiten Weltkrieg nördlich der Donau erlitt die Leopoldauer Pfarrkirche kaum grössere Schäden und ist daher ein besonders authentisches Beispiel des Kirchenbarocks aus dem späten 17. Jh. Das Innere erscheint verhältnismässig schlicht. Der Hochaltar setzt sich aus einer grossen Kreuzigungsgruppe und dem Tabernakel zusammen. Dieser wird von zwei Putti flankiert und hat einen prächtigen barocken Aufsatz. Der Kanzelkorb ist üppig gestaltet und auf dem Schalldeckel prangt eine Friedenstaube im Strahlenkranz.