Palægade har navn efter et forlystelsessted, Palæhaven, som indtil omkring 1870 lå her.
Det hed sådan, fordi det lå i haven til Thotts Palæ på Kongens Nytorv. Beværtningen kaldtes dog i 1800-tallet også bl.a. Østrups Have. Stedets specialitet var stegte lammehoveder.
Før stedet lukkede i 1870, blev der holdt store fester, hvor haven var illumineret og der blev opstillet en dansestrade, men her havde dog kun “velklædt publikum” adgang.
Haven, der hørte til palæet på Kongens Nytorv, lå ikke vinkelret på de omliggende gader. Selv om haven blev nedlagt, definerede den langt op i tiden ejendomsskellene i området, og derfor fik Palægade sit skrå forløb.
Palæets have lå, hvor Palægade går i dag, og gadens skrå forløb, skyldes formentligt, at da arealet blev udstykket i slutningen af 1800-tallet, var det den mest hensigtsmæssigt at lægge gaden sådan, for at udnytte pladsen til byggeri af etageejendomme bedst muligt.
Den nuværende gade blev anlagt i slutningen af 1800-tallet, og inden da lå grosserer Jacob Crohns tømmerplads i området.
Både Palægade 1-3 og Palægade 2-4 er opført omkring år 1900 af ejendomsselskabet Palaisgaden, og er tegnet af arkitekterne Emil Blichfeld og Gotfred Tvede. På det nordlige hjørne mod Bredgade bæres husets kraftige hjørnetårn af en stor drage.
I Palægade 6 (herunder) havde kunstsamleren Christian Tetzen-Lund i mange år sin bopæl og kunstsamling, som var tilgængelig for offentligheden.
Ejendommen blev tegnet omkring 1900 af Philip Smidth (1855-1938).
