Hyskenstræde nævnes første gang i 1480, men er sandsynligvis ældre. Hvor strædet mødte stranden, lå fra 1281 byens vejerbod.
Gaden kan have fået sit navn efter det offentlige toilet, der tidligere lå for enden af gaden ved Gammel Strand.
Toilettet kaldtes for en hysken, som er en forvanskning af det tyske ord häusschen, der betyder “lille hus”.
Faciliteten har også været kaldt en mag, som indgår i gadenavnet Magstræde, hvor der også var et nødtørftshus.
Toiletbygningerne har formentlig ligget ude i stranden, så man ikke behøvede at tænke på afløb. Tidligere lå kysten langs den nuværende gader Farvergade, Kompagnistræde og Læderstræde.
I 1400-tallet syntes beboerne i gaden, at det ikke var særlig forment at gadenavnet henviste til et toilet. Derfor begyndte de at kalde gaden for Lasse Vinners Stræde, efter én af byens rådmænd.
Hyskenstræde kan dog også have fået sit navn efter tyske købmænd, der kaldte sig häuschner. Købmændene havde slået sig ned i gaden og på hjørnet af Vimmelskaftet lå den tyske handelskompagnis hus. Danskerne kaldte Hyskenstræde for Tyskernes Gade.
De tyske købmænd handlede bl.a. med krydderier og i 1486 solgte de for første gang de sjældne peber fra en bod i Hyskenstræde. Der blev naturligvis lagt en særlig peberskat på denne luksusvare.
På hjørnet af Hyskenstræde og Amagertorv lå i 1700-tallet Løveapotekets bygning, der var opført i 1796 med Caspar Frederik Harsdorff som arkitekt og bygmester.
Fysikeren H. C. Ørsted blev leder af apoteket.
Ejendommen brændte omkring 1907 og erstattet af den nuværende forretningsejendom. Den blev tegnet af arkitekterne Victor Nyebølle (1862-1933) og Christian Brandstrup (1859-1937) og er karakteristisk ved sine meget store vinduespartier.
I en årrække var der stadig apotek i bygningen og apotekerne begyndte i 1908 en industriel fremstilling af apotekervarer. Det blev starten på Løvens Kemiske Fabrik, som i 1920’erne flyttede til Brønshøjvej.