Der Bau entstand unter schlechten Bedingungen. Die Planung war mit der Diskussion um den Abbruch der barocken Floriani- und Rauchfangkehrerkirche verbunden, dem Wahrzeichen des 5. Bezirks, die mitten auf der Wiedner Hauptstrasse stand. Die Stadt Wien hatte der Erzdiözese das Grundstück für den Neubau mit der Auflage verkauft, die alte Kirche aus verkehrstechnischen Gründen abreißen zu können, was nach Jahren, unter heftigem Protest der Bevölkerung und der Medien, auch geschah.

Die „Österreichische Gesellschaft für Architektur” hatte sogar beim beginnenden Abbruch (August 1956) eine kurze Besetzung durchgeführt. Ein Wettbewerb für ein „Neues Wahrzeichen” an der gleichen Stelle, wie die alte Kirche, beendete dann (ohne Folgen) den traurigen Akt bornierter Stadtzerstörung durch die Stadt. (Friedrich Achleitner)
Ein internationaler Wettbewerb 1956 - für die Wiener Architektur von besonderer Bedeutung, da hier erstmalig die jüngere Generation mit Erfolg auftrat - entschied sich für Rudolf Schwarz, der den 2. Platz belegte (ein 1. Preis wurde nicht vergeben).

Den Bauplatz fand Schwarz wegen der hohen und unruhigen Nachbarbebauung schwierig. Eine „vollkommen einfache und kraftvolle Gestalt” schien ihm deshalb angemessen. Der Bau sollte 2.000 Gläubige aufnehmen und nicht nur groß sein, sondern auch groß erscheinen. Den kastenförmigen „Betsaal Gottes” prägen die baumartigen Wandstrukturen mit ihren Diagonalrippen, die statisch einen Gitterträger bilden. Die Lichtfülle des „leuchtenden Gewändes” wurde stark reduziert durch die dunkelfarbigen Fenster von Giselbert Hoke, die nach dem Tode von Schwarz - er starb bei Baubeginn - eingesetzt wurden.

In den niedrigen Seitenschiffen sollten die liturgischen Orte ursprünglich durch Lichthöfe ausgezeichnet werden. Sie wurden aber aus Kostengründen durch Oberlichtaufsätze ersetzt. (Wolfgang Pehnt)