Gaden har navn efter Gråbrødrekloster, der lå ved Gråbrødretorv.
Navnet er bevaret siden middelalderen, hvor gaden blev anlagt. Den nævnes i 1400-tallet, men gaden har nok eksisteret endnu tidligere.
På hjørnet af Skindergade lå bryggerlaugets hus. Bygningen var en rest af det tidligere kloster, men forsvandt ved branden i 1795.
I 1700-tallet var Klosterstræde domineret af skomagere, op på et tidspunkt boede hele 21 af dem her.
På hjørnet af Amagertorv ligger en stor forretningsejendom, der også har facade mod Valkendorfsgade. Bygningen blev opført omkring 1906 for Kjøbenhavns Laane- og Discontobank. Banken optog det meste af stueetagen, mens de øvrige etager var udlejet til andre erhvervsdrivende. Senere rummede den Haandværkerbanken i København.
Kommunens stillede som betingelse for byggeriet, at byggelinjen mod Klosterstræde blev rykket tilbage. Dermed opstod en gård, der dog i stueplan blev overdækket, så der kunne indrettes butikker (billedet herunder). Bygningen er tegnet af arkitekt Axel Berg (1856-1929).
