Larslejsstræde er opkaldt efter Laurids Lej, der ejede en grund i området i middelalderen.
Oprindeligt endte gaden blindt, og blev først efter 1500-tallet ført igennem til Nørrevold. Området lå i byens udkant og var domineret af haver, så her var kun spredt bebyggelse.
I 1600-tallet lå dengang huse for de fattige – de såkaldte sjæleboder.
Gaden var adgangsvejen til Sankt Petri Kirkes kirkegård og til en gård der tilhørte Skt. Johannes og Skt. Birgitte alter.
Ved Larslejsstræde lå indtil bybranden i 1728 en lille gade, der kaldtes Pædagogistræde efter en gård (Pædagogigården) på hjørnet af Larslejsstræde og Sankt Peders Stræde. Her boede én af professorerne ved Københavns Universitet.
Larslejsstræde har været præget af Sankt Petri Kirkes institutioner. I gaden lå flere stiftelser, der hørte til kirken.
Hvor Pædagogigården lå, ligger nu Sankt Petri Kirkes tidligere præstegård.
I Larslejsstræde 5 (herover) ligger den tyske skole, der kan føre sin historie helt tilbage til 1575, hvor den hed Sankt Petri Chorschule.
Dengang var den én blandt flere tyske skoler i København, for en betragtelig del af byens indbyggere var tysksprogede.
Skolen var oprindeligt for drenge, men fik i 1700-tallet også tilknyttet en realskole for piger. I dag fungerer den som en tysksproget privatskole.
Ved siden af i Larslejsstræde 7 ligger en anden afdeling af skolen. Den trefløjede bygning (herover) blev opført omkring 1898 til Pelts Plejestiftelse.
Den var grundlagt i 1779 af sukkerfabrikanten Abraham Pelt som et plejehjem for ældre. Over indgangsdøren sidder en mindetavle fra stiftelsens oprindelige bygning,
Begge bygninger er tegnet at arkitekten Frederik Levy (1851-1924)
I Larslejsstræde 11 ligger Brødrene Petersens Jomfrukloster (herover).
Det blev stiftet i 1755 og har haft til huse flere steder i byen, bl.a. på Amagertorv, men flyttede hertil i 1918.
Stiftelsen havde – og har – til opgave af stille lejligheder til rådighed for klosterdamerne, de såkaldte konventualinder, samt deres priorinde.
Bag Larslejsstræde 11 lå Frederik den 6.’s asyl. Asylet flyttede i 1937 til Sankt Peders Stræde.
I gården lå også Larslejsstrædes Skole, der var bygget i 1850 med P. C. Hagemann som arkitekt. Skolen indgik senere i Nørrevold skole i Nørre Voldgade.