Hvor gaden møder Kompagnistræde lå i 1300-tallet Strandbadstuen, der var den ene af Københavns tre offentlige bade.
De to andre lå ved Vestergade og ved Sankt Nikolaj Kirke. Her kunne byens befolkning blive vasket, men også barberet og behandlet for mindre sygdomme.
Badstuen var beregnet for begge køn, der efter datidens normer godt kunne bade sammen. Der var også udskænkning, så her har givetvis været et lystigt liv. Badstuen blev lukket i 1509, fordi man var bange for at syfilis kunne spredes herfra.
Gaden er én af det indre Københavns ældste. Den nævnes i roskildebispens jordebog fra 1377, hvor der hedder at der findes kødmanger-boder – altså udsalg af slagterivarer – i strædet. De blev dog omkring 1400 flyttet til Købmagergade.
I gården til Badstuestræde 18 er der muligvis i kælderen en rest af muren til det gamle kompagnihus for Danske Kompagni, der lå i Kompagnistræde.