Gaden hed indtil 1818 Skidenstræde, måske fordi “Byens Rende” – en åben kloak – løb gennem gaden. I kvarteret boede en del af byens socialt dårligt stillede.
Da gaden blev brolagt – eller “krystalleret”, som man kaldte det – brugtes også navnet Cristal Gaden. Da kloakrenden blev nedlagt i 1818. bad beboerne om af få navnet ændret til Krystalgade.
Ved Skidenstræde lå i 1600-tallet den lille Hattemagerens Gang, der nu er forsundet.
I dag ligger bl.a. Københavns Synagoge, det tidligere Zoologisk Museum og Københavns Hovedbibliotek i Krystalgade. Biblioteket lå indtil 1993 på Kultorvet.