Et gammelt hus
Arbejdsdirektoratets nuværende domicil, Stormgade 10 - også kendt som Det Holsteinske Palæ - er en historisk bygning med rødder helt tilbage til sidste halvdel af 1600-tallet. Dengang var kvarteret nyt, og hofmarskal H. Lutzow købte en grund og lod opføre et toetagers palæ, som blev kernen i det senere Holsteinske Palæ. Grunden strakte sig fra Stormgade til Løngangsstræde.
Slægten Holstein
I 1726 kom ejendommen i slægten Holsteins eje. I 1730 blev Johan Ludvig von Holstein (senere Holstein-Ledreborg) ejer af ejendommen. Han var Christian d. VI´s gehejme-etatsminister (statsminister) og senere lensgreve til Ledreborg ved Lejre. Palæet i Stormgade var hans vinteradresse, mens han boede på Ledreborg om sommeren.
I Johan Ludvig von Holsteins tid gennemgik palæet ca. 1756 en større ombygning efter hofbygmester Jacob Fortlings planer, hvorved det fik sin nuværende udformning som et karakteristisk barokanlæg med strengt gennemført symmetri i såvel plan som facader. Hovedbygningen blev samtidig forhøjet med en etage.
Det indre af palæet blev også bygget om ved samme lejlighed, bl.a. blev den herskabelige italienske marmorvestibule og -trappe indrettet til venstre for porten.
I kongens eje
Huset gik ud af slægten Holstein i 1807 og havde en række skiftende ejere indtil 1827, hvor det blev købt af Frederik d. VI. Kongen havde tænkt sig, at hans svigersøn, arveprins Ferdinand, skulle bo i palæet, og lod det derfor ombygge og modernisere af arkitekten Jørgen Hansen Koch.
Skiftende beboere indtil i dag
Det blev imidlertid Zoologisk Museum, der tog palæet i brug indtil 1870. I 1872 blev det erhvervet af Den almindelige brandforsikring for Landbobygninger, som lod palæet restaurere og modernisere i 1939.
I dag tilhører ejendommen staten sammen med naboejendommene. Stormgade nr. 12 er oprindelig opført omkring 1680, men har fået sin nuværende senklassiske facade midt i 1800-tallet. Stormgade nr. 8 er bygget i 1737-38 og består egentlig af to huse, der blev sammenbygget i 1748 og fik sit nuværende udseende i 1845. Nr. 8´s rokokoport og -trappe minder stadig om husets fortid.
Stormgade var krigsskueplads
Selve Stormgade har sit navn efter det svenske stormangreb på København, der fandt sted natten mellem den 10. og 11. februar 1659. Svenskerne kom over isen, og kampene fandt sted syd for Slotsholmen, hvor Kalveboderne nåede helt ind til det, der i dag er Stormgade.