Indtil 1818 hed gaden Skidenstræde. Den var anlagt oven på bækken, som via Kristen Bernikows Gade løb ud i stranden - eller rettere: Lille Skidenstræde gik fra Nørregade til Fiolstræde og Store Skidenstræde fra Fiolstræde til Købmagergade.

Krystalgade havde tidligere det delikate navn Skidenstræde, hvilket har sin tilsyneladende naturlige forklaring i den flere gange omtalte "Byens Rende", den åbne grøft eller kloak, som optog overfladevand og afløbsvand godt blandet med skarn af enhver art og førte dette fra de højereliggende dele af byen ud til stranden. Renden tog sin begyndelse ud for Petri Kirkes kor og løb så østpå. Sidst i 1400-tallet var rendens funktion som afvandingsledning udspillet, og en række smalle stræder opstod i stedet. Disse stræder var dog endnu i mange år ret uvejsomme på grund af pløre og ælte. Mens de andre gader, der opstod i sporet af "Byens Rende", fik ganske nette navne som Landemærket, Vognmagergade og Christen Bernikowsstræde, klæbede der gennem århundreder al den med renden forbundne stank og snavs til navnet Skidenstræde. Det er tydeligvis et navn, der er opstået i folkemunde og så blevet hængende. I officielle papirer har strædet til midt i 1500-tallet forskellige omstændeligt beskrivende betegnelser såsom "det stræde som løber ad Nørregade og hart bag om bispens gård af Sjælland" (1496) eller "byens stræde og rende, som løber fra Nørregade og ned til Rosengården" (1504).