Gaden blev anlagt efter reformationen i 1536, hvor den blev kaldt Ny Gråbrødrestræde efter Gråbrødrekloster, der lå tæt ved. Gaden blev adgangsvej til det palæ, som Corfitz Ulfeldt opførte på det tidligere klosters grund.
Der fandtes allerede en gade med navnet Gråbrødrestræde (den nuværende Skindergade).
Gaden hed oprindeligt Løvestræde, som med tiden blev til Løvstræde. Forklaringen på navnet fortaber sig i det uvisse.
