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.
For enden af Hyskenstræde gik kysten engang, og her lå ét af Københavns offentlige toiletter, som måske har givet gaden sit navn.
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.
Hyskenstræde nævnes første gang i 1480, men er sandsynligvis ældre. Hvor strædet mødte stranden, lå fra 1281 byens vejerbod.