Ende August 1893 wurde mit den Fundierungsarbeiten begonnen. Die gesamten Bauarbeiten standen unter der Leitung des renommierten Hofbaumeisters Josef Schmalzhofer, der zahlreiche Kirchenbauten in Wien betreute. Doch selbst für ihn war die Errichtung eines 60 Meter langen und 32 Meter breiten Kirchenschiffes mit einem Fassungsvermögen von bis zu 2200 Personen eine Herausforderung.
Wielemans beschreibt den Bau nach dessen Fertigstellung wie folgt:
Die Kirche ist in konstruktiven Ziegelrohbau, in Renaissanceformen, anschließend an die Frührenaissance-Ziegelbauten in Oberitalien, mit einigen Verputzflächen und möglichster Vermeidung von Hausteinarbeiten durchgeführt worden. Ebenso sind eigentliche Terracotta-Verkleidungen hauptsächlich nur zur Frieseinlagen verwendet worden; diese, der älteren strengeren Auffassung des Zielrohbaues entsprechende Durchführung erforderte eine große Zahl (44 Nummern ohne Eckstücke) von Formsteinen (sämtliche von der Wienerberger Baugesellschaft geliefert). Auch die Pfeiler im Innern sind in einfach geschlemmten Ziegeln mit Portlandzement hergestellt worden. Das tonnenförmige, mit Schildern gezierte Mittelschiffgewölbe ist mit nicht sichtbaren Verstärkungsgurten aus porösen Ziegeln, 15 cm stark, hergestellt. Die Dächer der Kirche, die beiden Turmhelme und das Sanktustürmchen sind in Eisenkonstruktion von der Firma Ignaz Gridl hergestellt worden. Unterkellert sind die Teile zwischen den beiden 63 Meter hohen Türmen, welche auf einer 1,6 Meter hohen Betonplatte ruhen und der Raum unter dem Presbyterium und den beiderseiten Anbauten.
Bereits im November 1895 ragten die beiden Türme als Rohbau in die Höhe. Danach begann der heikelste Part: die Überdachung des Kirchenschiffs. Dabei stürzte am 4. April 1896 um die Mittagszeit ein Tonnengewölbe von ungefähr 8 Meter Breite und 13 Meter Spannweite ein. Die Ziegel blieben auf dem obersten Teil des Gerüstes liegen. Da kurz vorher die Mittagspause begonnen hatte, wurde kein Arbeiter verletzt. Dies sollte jedoch leider nicht der einzige Bauunfall bleiben. Im November desselben Jahres stürzte der 32jährige Glasergehilfe Rudolph Gehring während er die Verglasung der Kirchenfenster vornahm von einem 6 Meter hohen Gerüst in die Tiefe. Das gleiche Schicksal ereilte eineinhalb Jahre später traurigerweise auch dem Maurer Joseph Zischka, der schwer verletzt in das Allgemeine Krankenhaus gebracht wurde. Auch der Sturm vom 1. Februar 1898, der in ganz Wien enorme Verwüstungen hinterließ, setzte dem Bau mächtig zu und wurde gleich zur ersten Bewährungsprobe. Der Wind brachte dabei sogar die sieben Glocken zum Klingen. Diese hatten ein Gesamtgewicht von 6000 Kilogramm und ertönten bereits am Freitag dem 22. Mai 1896 um 15 Uhr „im schönsten harmonischen Einklange“.
Da die Bauarbeiten zügigervorangingen als erwartet, zeichnete sich schon bald die Möglichkeit ab, die Kirche im sogenannten Jubiläumsjahr (50. Thronjubiläum des Kaisers Franz Joseph I.) einzuweihen.
