Wo die heutige Kirche steht, hat bereits im 13. Jrh. eine Muttergotteskapelle existiert, welche im Besitze der Deutschen Ordensritter war, dann aber an das Stift Klosterneuburg überging. In den Jahren 1414-1419 wurde eine neue Kapelle im gotischen Stil erbaut, welche jedoch in den folgenden Jahrhunderten mehrmals durch die Türkenbelagerungen und die Angriffe der Ungaren verwüstet wurde. Um 1685 wurde die Kirche nach Initiative des Klosterbeuburger Prälats Christoph Mathäi ebenfalls im gotischen Stil neu erbaut. In den folgenden Jahren wurde die Kirche mehrmals ausgebaut, erweitert und im Inneren barockisiert. Die reich stuckierte Decke ist das Werk von Dominicus Piazzol, und die Fresken stammen von Antoni Galliardi. Sämtliche Bildnisse zeigen Szenen aus dem Leben Mariens von der Erwählung bis hin zur Grablegung.

Um 1698 errichtete Matthias Steinl den beachtlichen Hochaltar, welcher um 1751 seine endgültige Form erhielt. Die Gnadenstatue im Zentrum des Hochaltars, welche noch heute verehrt wird und die Kirche zur Wallfahrtsstätte machte, geht auf folgende Sage zurück:

Während der ersten Türkenbelagerung Wiens im Jahre 1529 wurde die Kirche ein Raub der Flammen. Es gelang jedoch, die Marienstatue vor den Flammen zu retten und in der Krone eines Baumes zu verstecken. Die Türken fuhren fort, alle Einwohner niederzumetzeln oder zur Sklaverei zu verdammen. Vier Hietzinger wurden von den Türken mit Ketten an den besagten Baum gefesselt und da ihrem Schicksal überlassen. Nach dem Abzug der wütenden Meute war keine Menschenseele mehr weit und breit. Alle Hilferufe der Angeketteten nützen nichts, den kein Mensch konnte sie hören und befreien. Sie sahen keinen anderen Ausweg, als zur Heiligen Maria zu beten und um Erlösung zu Flehen. Da erleuchtete die Marienstatue plötzlich in hellstem Glanze und tauchte den ganzen Baum in ein gleissendes Licht. Und schon fielen die Ketten der Gefangenen rasselnd zu Boden, und sie waren frei. Gleichzeitig hörten sie eine Stimme rufen: „Hütt’s eng“ (Hütet euch). Die Befreiten versteckten sich im nahen Walde und kehrten kurz darauf wohlbehalten zu ihren Familien zurück. Der Name Hietzing soll gemäss dem Volksmund von „Hütts’eng“ abgeleitet worden sein.

Diese Szene ist in Hochaltar dargestellt: Der grüne Laubkranz um die Gnadenstatue symbolisiert die Baumkrone, links und rechts des Tabernakels stehen die Figuren der Erretteten. Die vier grossen goldenen Figuren links und rechts der Szene stellen die heiligen Joachim und Anna (die Eltern Mariens) und Elisabeth und Zacharias (die Eltern Johannes des Täufers) dar. Die beiden Seitenaltäre sind ebenfalls das Werk von Matthias Steinl. Die beiden darin enthaltenen Ölgemälde (links: Christus am Kreuz, rechts:  Der hl. Josef am Sterbebett) stammen von Michael Rottmayr aus dem Jahre 1712. Um 1690 wurde die Leopoldikapelle angebaut mit einem Altarbild des hl. Leopold, der einen Bauplan der Kirche St. Leopold am Berg in den Händen hält.

Um der wachsenden Zahl der Pilger weiterhin zu genügen, wurde um 1733 die Johannes Nepomuk-Kapelle angebaut, in welcher sich ein Ölgemälde befindet, welches den Heiligen auf seiner Wallfahrt nach Alt-Bunzlau zeigt.

Die Kirche Maria Hietzing war die Lieblingskirche Maria Theresias. Oft kam sie hierher, um in einem seitlichen Chorraum ungesehen der Messe beizuwohnen. Im Jahre 1762 stiftete sie der Gemeinde Hietzing ein mit Silber beschlagenes und mit Blumen verziertes Kleid für die Gnadenstatue. Dieses wurde allerdings um 1809 wieder entfernt und eingeschmolzen.

In den Jahren 1863-1865 erhielt die Kirche eine Erweiterung, in deren Rahmen die Westfassade und der Glockenturm von Carl Rösner im neugotischen Stil errichtet wurden. 1945 trafen zwei Bomben die Kirche und beschädigten sie erheblich. Zwei Jahre nach Kriegsende wurden die Schäden vollständig behoben. In den Jahren 1994/95 wurde die Kirche aussen umfassend renoviert, von 2003-2005 erfolgte eine gründliche Innenrenovation.