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. Udsnit af Geddes kort fra 1757.
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 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.
Hjørneejendommene ud mod Bredgade, er Palægades mest markante. 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 bæres husets kraftige hjørnetårn af en stor drage.