Der Karmeliterorden wurde 1360 von Herzog Rudolf Stifter nach Wien berufen. Sie bauten im Jahre 1386 am Hof eine Kirche, die Kirche am Hof. durch die Reformation ging der Karmeliterorden jedoch unter, und die Kirche wurde den Jesuiten übergeben.
Um 1620 wurde der Orden von Kaiser Ferdinand II. erneut nach Wien berufen. Dieser übergab den Karmelitern für den Bau eines Klosters mit Kirche einen Platz im "Unteren Werd enthalb der Schlagbrücken" 1639 wurden das Kloster und die heutige Pfarrkirche St. Josef errichtet. Während der Türkenbelagerung brannte das Kloster nieder, und die Kirche wurde stark beschädigt. Nach der Rettung der Kirche und deren Instandsetzung errichtete man auf dem Platz davor eine Dreifaltigkeitssäule.

Weitere Beschädigungen erlitt die Kirche während der Napoleonischen Kriege, bei Überschwemmungen der Donau im März 1830 und bei der Revolution von 1848. 1901 zogen die verbliebenen Angehörigen des Karmeliterordens nach Döbling über.
Das alte Kloster wurde 1910 abgebrochen und an den Chor der Kirche das Pfarrhaus angebaut. Wie viele andere Bauwerke erlitt auch die Karmeliterkirche im Zweiten Wetlkrieg schwere Schäden durch die Bombenniedergänge. Diese konnten jedoch 1961 gänzliche behoben werden. Am 7. Dezember 1961 wurde die Kirche durch Kardinal Dr. Franz König feierlich wiedereröffnet.