Die ursprüngliche Kirche zur „Lieben Frau auf der Gestetten“ war die Kirche der Donauschiffer. Laut einer Sage wurde sie von Bischof Maldavin aus Passau erbaut. Urkundlich erwähnt wurde die Maria-Stiegen-Kirche erstmals im Jahre 1158. Der Namensteil „Gestade“ hat jedoch nicht in erster Linie etwas mit Stiegen zu tun, sondern vielmehr bezeichnet „Gestade“ das Ufer der Donau. Die Kirche steht am Abhang zu einem einstigen Seitenlauf der Donau - heute am oberen Ende einer Freitreppe.
Um 1332 begann man mit dem Bau eines einschiffigen Chortraktes mit polygonalem (vieleckigem) Grundriss. Im Jahre 1394 legte der Hofmeister Herzog Albrechts III., Hans von Liechtenstein-Nikolsburg, den Grundstein zu einem ebenfalls einschiffigen, noch schmäleren Langhaus, welches in einem leichten Winkel zum Chor steht. Die schlanke Form entstand aufgrund der dichten Verbauung rund um die Kirche. Die Deckengewölbe - Werk der damaligen Dombauhütte unter Peter Prachatitz - bestehen aus einem zusammenhängenden Rautennetz aus Knickrippensternen. Anfang 15. Jrh. erbaute man die 33m hohe und gerade mal 10m breite Westfassade.

Der Giebel fällt besonders auf durch die üppigen Fialen (gotische Ziertürmchen meist mit abschliessender Kreuzblume), reichen Ornamente und Figurenbaldachine. Über dem Portal gleich unter dem mächtigen Spitzbogenfenster ist eine Steinkuppel angebracht mit rautensternartigem Gewölbe und mehrstufiger Kreuzblumenzinne. Der siebeneckige, 56m hohe Turm an der Südseite mit dem bemerkenswerten, durchbrochenen Helmdach wurde im Jahre 1430 vollendet. Die sieben Ecken verbildlichen die sieben Schmerzen Marias.
1786 wurde die Kirche entweiht und fortan dem Verfall überlassen. Da die Abbruchkosten zu hoch gewesen wären, liess man sie stehen und benutzte sie zeitweise als Pferdestall und Lagerhaus. Im Jahre 1812 begann man mit der umfassenden Restaurierung, worauf eine erneute Einweihung erfolgte. 1920 wurde Maria am Gestade Ordenskirche der Redemptoristen, welche mit Hilfe von Clemens Maria Hofbauer ausserhalb Italiens Fuss fassen konnten. Nach Hofbauers Tod wurden seine sterblichen Überreste in der Kirche in einem Schrein beigesetzt. 1909 erfolgte Hofbauers Heiligsprechung, und seit 1914 ist er Stadtpatron von Wien.