Um 1343 wird an der Stelle eine erste Kapelle erwähnt, welche dem hl. Theoblad und der hl. Katharina geweiht war. Zehn Jahre später wurde das angrenzende Spital in ein Kloster umgewandelt, welches während der ersten Türkenbelagerung 1529 zerstört wurde. Um 1661 bauten die Karmeliter hier ein neues Kloster, welches jedoch in der zweiten Türkenbelagerung 1683 ebenfalls zerstört wurde. Ein weiterer Neubau des Klosters erfolgte in den Jahren 1687-1697, dessen barocke Kirche dem hl. Josef geweiht wurde. Um 1797 wurde die Karmeliterniederlassung im Laimgrubenviertel aufgehoben und um 1804 im Kloster eine Erziehungsanstalt für junge Adelige eingerichtet. Am 24. November 1828 heiratet Joseph Lanner in der Kirche St. Josef Franziska Jahus. 1856 liess Kaiser Franz Josef I. hier ein Knabenseminar einrichten, welches um 1881 nach Hollabrunn verlegt wurde. Anschliessend nutzte man das Klostergebäude als polizeiliches Gefangenenhaus.

Noch im selben Jahr wünscht der damalige Bürgermeister Karl Lueger eine Verlegung der Kriche, denn da diese in die Mariahilferstrasse hineinragte, stellte sie ein Hindernis dar. Der Vorschlag, wie bei der Stiftskirche einen Fussgängerdurchgang unter der Orgelempore zu schaffen, wurde nicht angenommen. So entschied man im Jahre 1905 schliesslich, eine stilistisch möglichst identische neue Kirche etwas versetzt zu erbauen, deren Grundsteinlegung am 5. Mai 1906 erfolgte. In der folge wurde die ganze barocke Innenausatattung der alten Kirche und auch der Fassadenschmuck in die neue übertragen bis auf zwei Altäre, welche aufgrund einer leicht veränderten Grundfläche der neuen Kirche keinen Platz fanden. Ein Brand beschädigte und verwüstete 1999 grössere Teile im Inneren der ehemaligen Karmeliterkirche, was aber innerhalb der folgenden Monate wieder instand gestellt werden konnte.

Die Kirche liegt heute versteckt etwas abseits der Mariahilferstrasse. Ihre Fassade mit den von Zwiebelhelmen bedachten Doppeltürmen steht an der Windmühlgasse. Ionische Pilaster gliedern die Fassade mit den Steinfiguren von Elias, Elisäus und des hl. Josef am oberen Ende der Front. Die Laimgrubenkirche St. Josef ist eine dreijochige Saalkirche mit Seitenkapellen. Der Aufbau des Hochaltars aus dem späten 18. Jrh. ist nach spätbarocker Form konzipiert und die Kanzel aus der 2. Hälfte des 18. Jrh. klassizistisch. Die Decke ist im Chorraum wesentlich reicher stuckiert als im Kirchenschiff.