Larslejstræ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 Larslejstræ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 Larslejstræde og Sankt Peders Stræde. Her boede én af professorerne ved Københavns Universitet.
Larslejstræ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, der ses til højre på billedet herover.
I gaden 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.
