Gaden har eksisteret siden middelalderen, og har navn efter et herberg (eller hospital) og et kapel, der var viet til Sankt Gertrud. Kapellet nævnes i 1440’erne, og hospitalet i 1520’erne.
Kapellet lå på hjørnet af Kultorvet og Sankt Gertruds Stræde, men blev formentlig nedlagt i 1530’erne, hvor det blev lagt sammen med Helligåndshuset.
Til kapellet hørte også en kirkegård, og her lå et rettersted, hvor kong Christian den 2.’s lensmand, Torben Oxe, blev henrettet i 1517, fordi han var anklaget for at have myrdet kongens elskerinde, Dyveke.
En del af gadens huse er opført efter bybranden i 1728 og er blevet fredet.
Gertrud var abbedisse i et fransk nonnekloster i 600-årene. Hun var kendt både som kirkebygger og for hendes godgørenhed overfor de syge, og derfor blev hun kåret som helgeninde. Udtrykket at “Glansen er gået af Sankt Gertrud”, betyder formentlig, at man kan godt ære en helgen, selv om forgyldningen af hendes billede er slidt af. (Udsnit af altertavle på Nationalmuseet).
