Gaden er opkaldt efter byens offentlige mag, som er et gammelt navn for et toilet. Det stod på pæle i strandkanten, som fulgte gadens forløb. For enden af Hyskenstræde var et tilsvarende nødtørftshus.
Gaden opstod i 1520’erne, da man flyttede kystlinjen længere ud. Før gik den langs det gadeforløb, der i dag dannes af Farvergade, Kompagnistræde og Læderstræde.
Magstræde fik i 1800-tallet et dårligt ry, fordi det var en gade for især de lidt ældre prostituerede.
I Magstræde 17-19 ligger nogle af de få huse i København, som er bevaret fra Christian den 4.’s tid. De er bygget ca. 1640.
På facaden er sandstensbånd og buestik over vinduer tegn på datidens byggeskik.
