Alléen har navn efter Lersøen, der lå mellem Nørrebrogade og Lyngbyvej.
I 1910 startede projekteringen af en bred gade, der skulle gå fra Jagtvej mod nordvest. Idéen var at give københavnerne en let mulighed for at komme ud til de rekreative områder i Utterslev Mose.
Vejen kom i første omgang til blot at hedde Parkalléen og senere Klædebo Parkallé. Den blev anlagt i slutningen af 1930’erne.
Klædebo var betegnelsen for ét af kvarterene i Indre by, hvor klædehandlerne havde deres boder. Det var bl.a. i Skindergade. Senere fik området udenfor volden ved Østerport navnet Udenbys Klædebo Kvarter.
Længere ude i bydelen Emdrup lå en tilsvarende allé, der i 1930’erne havde fået navnet Lersø Parkallé.
De to dele af alléen blev sluttet sammen, da der blev bygget en tunnel under jernbanen ved Rovsinggade.