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. Omkring år 1900 var der bordeller i mindst seks huse i gaden og en femtedel af dens beboere ernærede sig ved prostitution.
I Magstræde 17-19 (herover) 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.
Magstræde 6 er opført af bygmester Philip de Lange (1704-1766) i 1730’erne.
Huset er opført for hofsnedker Didrik Schäffer, som dog lejede ud til bl.a. den kongelige livlæge Johann Friederich Struensee, så huset kaldes “Hofsnedkerens Gård” eller “Struensees Gård”. Den halvrunde fronton er tilføjet i 1800-tallet.
I Magstræde 3 (herover til højre) kan man se et eksempel på en meget gammel gadedør, som formentlig den oprindelige fra husets opførelse i 1730’erne.
I Magstræde 14 ligger et pakhus, der har hørt til handelsvirksomheden Sthyr & Kjær. Firmaet var involveret i handel med sukker, bl.a. fra Dansk Vestindien. Efterhånden engagerede man sig i detailhandel og dannede bl.a. grundlaget for købmandskæden Spar.
Sthyr & Kjærs bygninger i Magstræde har også omfattet ejendommen i Rådhusstræde 13 og hele komplekset blev i 1970 indrettet som et alternativt kulturhus under navnet Huset i Magstræde.
Også Magstræde 10 (herover) er et nyere pakhus. Her lå Magstrædes Dampmølle og C. I. Meyers Spritfabrik
Næsten alle huse i Magstræde er fredede.