Л. Лещенко родился 1 февраля 1942 года в Москве (на 2-й Сокольнической улице) в семье военнослужащего. Его детство выпало на первые послевоенные годы, о которых он вспоминает так: «Меня воспитывала приемная мать — замечательная женщина! Жили мы в старом московском дворике, и жили очень дружно. Если у кого-то во дворе появляется велосипед, на нем по очереди катаются все ребята двора. Если кто-то покупает косном, приходят смотреть все соседи. И радость каждой покупки — общая. Ну а если ты голоден, а родители еще на работе, кто-нибудь из соседок обязательно тебя накормит. Жили, конечно, трудно, но открыто, щедро друг для друга».
Еще будучи ребенком, Лещенко решил, что обязательно станет артистом. Поэтому свое восхождение к славе он начал с районного Дворца пионеров, где записался сразу в два разных кружка: хоровой и драматический. В одном он с удовольствием пел, в другом с таким же упоением читал стихи. Судя по тому, что вскоре его стали брать на все районные и городские смотры художественной самодеятельности, занятия в обоих кружках шли ему на пользу.
Между тем к окончанию десятилетки Лещенко окончательно определился со своим выбором и решил посвятить себя музыке. Накупив в магазине пластинок Франко Карелли, Марио Дель Монако и других популярных исполнителей, наш герой с утра до вечера крутил их на своей радиоле, после чего с дотошностью прилежного ученика пытался самостоятельно воспроизвести услышанное. На его взгляд, получалось неплохо. В конце концов, преисполненный самых радужных надежд, Лещенко после окончания школы в 1959 году отправился в ГИТИС — поступать на отделение артистов оперетты.
К сожалению, тот поход закончился неудачей — Лещенко в институт не приняли. Видимо, на фоне других абитуриентов он выглядел не столь убедительно, поэтому экзаменаторы провалили его со спокойной совестью. Пришлось Лещенко ждать целый год, чтобы поискать счастья в новой попытке. Год прошел незаметно, тем более что все это время Лещенко не бил баклуши, а трудился сначала рабочим сцены в Большом театре, а затем ушел на завод точных приборов слесарем.
Как это ни странно, но и вторая попытка будущего народного артиста России попасть в ГИТИС завершилась провалом. Экзаменаторы вновь не нашли в нем ничего примечательного и завернули с первого же захода. После этого любой другой на месте Лещенко наверняка пришел бы к грустной мысли о несоответствии своего таланта выбранной специальности. То есть занялся бы чем-нибудь другим. Но, будучи человеком настойчивым, он поступил в соответствии со своим характером — пришел на очередные экзамены в ГИТИС через год после второго провала.
На этот раз Лещенко сдавал экзамены намного успешнее, чем в два предыдущих раза. Тур за туром он шел к заветной цели — стать студентом — и наверняка бы им стал, если бы и на этот раз случай не вмешался в течение событий. Дело в том, что к тому времени пришла пора молодому человеку служить в армии, и пришедшая из военкомата повестка наглядно это продемонстрировала. Вот и пришлось Лещенко вместо того, чтобы сесть за парту, становиться к орудийному расчету — он попал в танковые войска и в качестве заряжающего танка проходил службу в ГДР.
Стоит отметить, что занятия вокалом новобранец не прервал и в армии. Вскоре о его способностях прознало армейское начальство и пристроило Лещенко солистом в ансамбль песни и пляски. В этом качестве он и закончил свою службу в армии. А вернувшись на гражданку, он в четвертый (!) раз пришел на экзамены в ГИТИС и все-таки добил своим упорством преподавателей — несмотря на огромный конкурс (46 человек на место), его приняли на отделение музыкальной комедии (преподаватель — Георгий Павлович Анисимов).
Во время учебы в ГИТИСе в жизни Лещенко произошло сразу несколько заметных событий. Во-первых, в 1969 году, будучи студентом 3-го курса, он женился на своей однокурснице Анне Абдаловой, во-вторых, он стал пользоваться успехом как солист. Сначала его пригласили в Московский театр оперетты в качестве бас-баритона, определив ему оклад в 110 рублей (другим начинающим певцам платили всего лишь 90 рублей), а в 1970 году он получил приглашение стать солистом вокальной группы Гостелерадио СССР.
Так ступенька за ступенькой артист шел к своей славе. Причем путь этот был отнюдь не таким гладким, как может показаться на первый взгляд. Много разочарований, обид и даже трагических случайностей поджидало его на этом пути. Например, и 1970 году Лещенко едва не погиб в авиационной катастрофе. Он тогда должен был лететь вместе со своими музыкантами и популярным в те годы пародистом Виктором Чистяковым на гастроли на юг, однако Гостелерадио его из Москвы не отпустило, нкиду его участия в творческом вечере поэта Льва Ошанина. И самолет улетел без него, но до места назначения так и не долетел — разбился.