Auch sie beansprucht, zu den ältesten Kirchen Wiens zu gehören. Sie trug ursprünglich den Namen "Unsere Liebe Frau auf der Gstetten", woraus sich ergibt, daß die Kirche außerhalb des verbauten Gebietes errichtet wurde. Um 880 soll an ihrer Stelle ein von Donauschiffern gebautes, hölzernes Kirchlein gestanden haben. Urkundlich erwähnt wurde sie erstmals im Jahr 1200, wo sie bald nach der Gründung der Schottenkirche den iro-schottischen Mönchen übereignet wurde. Die ursprünglichen Gründer, die Passauer Bischöfe, übernahmen ab 1302 wieder ihre Rechte an ihr.

1391 tauschten die Mönche die Kirche. So kam sie in den Besitz von Freiherr Hans von Lichtenstein-Nikolsburg, der den Neubau der Kirche veranlaßte. Die beschränkten Platzverhältnisse sowie der exponierte Steilabhang zur Donau bewirkte, daß das Langhaus schmäler als der Chor wurde und einen leichten Achsenknick aufweist. Sehr beeindruckend ist die überschlanke, 33 m hohe, aber kaum 10 m breite gotische Westfassade. Mit seinen 56 m Höhe war der Turm, der sich auf deinem siebeneckigen Grundriß erhebt, für die Donauschiffer ein weithin sichtbarer Orientierungspunkt, speziell durch seinen weißen, kuppelartig gestalteten, mit zarter Maßwerksarbeit durchbrochenen Steinhelm (1394 - 1414). Die Zahl 7 weist auf die sieben Schmerzen Marias hin.

Im Bereich des Chores wirkte Michael Knab, während den übrigen Bau der damalige Leiter der Wiener Dombauhütte, Peter Prachatitz über hatte.

Über dem Eingang füllt ein gewaltiges Spitzbogen-Fenster fast die gesamte Wand, wodurch die Fassade wie ein großes hochgezogenes Portal wirkt. Dort befindet sich auch die reliefartige Darstellung der beiden Johannes (um 1410). Beim Portal des Chores sollte man die Steinreliefs beachten: eine Schutzmantelmadonna und die Krönung Marias.

Im Inneren wirkt das Schiff eher düster, der Chor jedoch heller. Die Innenausstattung stammt überwiegend aus dem 19. Jhdt., doch einige Dinge sind älter: die Orgelempore (1515), der Renaissance-Altar in der Perger-Kapelle (um 1520), die Bauinschrift am Triumphbogen "1414" sowie vier Kirchenfenster im Chor, die aus alten Fenstern des 14. und 15. Jhdts. zusammengesetzt wurden. Sie sind so schön, daß einige von ihnen aus Laxenburg "repatriiert" werden mußten, wohin sie Kaiser Franz I. entführt hatte, um sein geliebtes Schloß damit zu verschönern.

Der Steilhang machte es erforderlich, eine breite Freitreppe zum Tiefen Graben hinunter zu bauen, die der Kirche den volkstümlichen Namen "Maria Stiegen" einbrachte.

1409 kam das Gotteshaus abermals zurück an das Bistum Passau. 1469 wurde das Wiener Bistum gegründet, doch "Maria am Gestade" blieb darin eine Enklave. Bis zu dieser Zeit war sie eine Kirche der Schiffer.

1786 wurde sie entweiht, geschlossen und verfiel zusehends. Stark vom Abriß bedroht war sie unter Joseph II., der an ihrer Stelle lieber das Versatzamt gesehen hätte. Die Demolierung wäre jedoch zu teuer gekommen, also ließ der Magistrat das vernachlässigte Objekt stehen.

Während der napoleonischen Kriege diente die Kirche als Pferdestall und Militärmagazin.
1812 wurde sie restauriert und neu geweiht.

1920 gelangte sie in den Besitz des Redemptoristenordens. Clemens Maria Hofbauer engagierte sich dafür, diesen Orden außerhalb Italiens zu verbreiten. Als er gestorben war, wurde sein Seligsprechungsprozeß eingeleitet und gleichzeitig seine Gebeine in die Kirche "Maria am Gestade" überführt. Dort setzte man sie in einem Reliqueinschrein bei. 1987 fertigte der Bildhauer Oskar Höfinger einen Reliquienaltar aus Kärntner Marmor an, neben dem nun aufrecht die Grabplatte steht, die vorher auf Hofbauers Grab in Maria Enzersdorf gelegen ist. 1909 wurde Hofbauer heilig gesprochen. Seit 1914 ist er Stadtpatron von Wien.

Leider darf die Kirche - wenn überhaupt - meist nur bis zu einem Abschlußgitter betreten werden, wodurch viele Objekte schwer zu erkennen sind.