Auf der Wieden stand bereits um 1211 eine Kirche, welche dem hl. Anton geweiht war. Kaiser Leopold der Glorreiche  schenkte die Kirche dem Orden des hl. Geistes. Im Jahre 1529 fiel die Kirche der Zerstörung der ersten Türkenbelagerung zum Opfer, worauf der ganze Orden zerstreut und seine Gesellschaft fast aufgelöst wurde. Um 1627 wurde unter Kaiser Ferdinand II. der Grundstein zu einer neuen Kirche gelegt. Da der Kaiser zur selben Zeit die Brüder vom Orden des hl. Franz von Paola, die Paulaner, nach Wien berufen hatte, wurde die neue Kirche auf Wunsch Ambrosius‘ de Renz, ein Gesandter der spanischen Niederlanden, diesen zur Verfügung gestellt. Gleichzeitig legte des Kaisers Thronfolger, Kronprinz Ferdinand, den Grundstein zu einem dazugehörigen Kloster.

Um 1651 war die Kirche fertiggestellt und wurde von Bischof Philipp Friedrich Graf von Breuner zu Ehren der heiligen Schutzengel geweiht. Als Wien um 1683 zum zweiten Mal von den Türken belagert wurde, liess Graf Starhemberg die Paulanerkirche und das Kloster zerstören. Es war eine Vorsichtsmassnahme, denn dadurch sollte verhindert werden, dass die Türken von hohen Gebäuden ausserhalb der Stadtbefestigung die Innenstadt unter Beschuss nehmen können. Nach der Belagerung baute man die Kirche und das Kloster im frühbarocken Stil wieder auf, wobei Architekt und Baumeister bis heute unbekannt geblieben sind, denn in der Pfarre wurden keine Dokumente hinterlegt. 1855 wurde hier der Leichnam August Lanners eingesegnet, nachdem dieser am 27. September im jungen alter von 20 Jahren verstorben war.
Die Fassade der Paulanerkirche ist schlicht gehalten, der barock ausgestattete Innenraum hat eine basilikale Form. Dieser gliedert sich in ein Langhaus mit Seitenkapellen, zwischen denen riesige Pilaster mit mächtigen Kapitellen die Architrave tragen.

Die gewölbte Decke im Langhaus ist schmucklos und reflektiert dadurch das eintretende Licht, was den Kirchenraum angenehm erhellt. Beeindruckend ist das grosse Deckengemälde im Altarraum, in dessen Zentrum die Friedenstaube im göttlichen Licht erscheint. Der breite Hochaltar mit seinem reichen figuralen Schmuck wurde von der Wiener Lakaienbruderschaft gestiftet und war im Jahre 1718 fertig gestellt. Sein Zentrum bildet das grosse Gemälde der Kreuzigung Jesu. Die beiden ovalen Gemälde über den mit Sprengwerk bekrönten Durchgangsporten in der Seitenkapelle mit dem Kreuzaltar wurden unlängst restauriert und konserviert. Sie zeigen eine Darstellung der Szene, in der ein Engel herangeeilten Frauen das leere Grab Christi zeigt und eine Darstellung von Christus als Gärtner. Die beiden Bilder sind Werke von Paul Troger und stammen aus dem Jahre 1745. Die Kanzel an der linken Seitenwand ist aus dunklem Holz angefertigt und weist auf dem Schalldeckel reichen vergoldeten Figurenschmuck auf. Im Kanzelkorb sind goldene Reliefs eingelassen.