Родился он 19 марта 1949 г. в деревне Усть-Уса Коми АССР. Его родители, Яков Степанович и Екатерина Ивановна, были ветеринарами, специалистами по оленям, поэтому детство мальчика прошло в разъездах по тундре.
Однако в 1961 г. врачи порекомендовали отцу сменить климат, и он с семьей перебрался в волжский городок Юрьевец, где Валера пошел в шестой класс. В школе он учился средне, на «4» и «3», правда, очень хорошо рисовал и любил сочинять для стенгазет научно-фантастические рассказы. Он уже тогда был очень артистичен, но сказать, что у него был какой-то прирожденный певческий талант, не решался никто. В то, что Валера станет известным, не верили. Над ним даже смеялись.
Он наряжался цыганкой, падал на колени, выпрашивал у директора школы белые туфли на каблуках и кольца, красил или приклеивал себе ресницы, завивал и без того кудрявые волосы… «Мы считали его своей подружкой, – рассказывала газетчикам одноклассница, когда-то участвовавшая с ним в художественной самодеятельности. – Не стеснялись и юбку поднять, чтобы подтянуть чулки, и лифчик застегнуть. Он и общался-то больше с нами, чем с ребятами. Они его били. А однажды один из них даже зажал Валерку в углу – не признал в нем, накрашенном и в женском костюме, парня. Пришлось спасать».
Настоящей мечтой Леонтьева была профессия океанолога. По окончании школы он хотел ехать сдавать экзамены в Дальневосточный университет, но этот план сорвался из-за отсутствия денег на проезд до Владивостока. Тогда Валера пошел по пути наименьшего сопротивления и отправился в близлежащую Москву. В том, что он поступит в ГИТИС, юноша не сомневался, поскольку считал себя опытным театральным актером. Но и тут ему встретились серьезные препятствия, одно из которых оказалось непреодолимым: стесняясь своего провинциального «оканья» и «стараясь произнести как можно меньше слов», Валерий забрал документы из приемной комиссии.
Когда не состоялась и вторая попытка остановиться на какой-то профессии, неудавшийся океанолог и актер вернулся домой и поступил рабочим на кирпичный завод, где катал вагонетки с сырьем. Чуть позже подобной работой занимался он и в Анапе, где какое-то время жили его родители. Затем работал тесемщиком-смазчиком на льнопрядильной фабрике в Юрьевце, сменил еще несколько профессий, и неизвестно, на какой окончательно остановил бы он свой выбор, если бы старшая сестра не решила, что пора брату получать высшее образование.
Таким образом Валера оказался в Воркуте, где работал лаборантом в НИИ оснований и подземных сооружений, затем – чертежником в проектном институте, а параллельно учился на вечернем отделении воркутинского филиала Ленинградского горного института. Разумеется, творческая натура Леонтьева не давала ему покоя и тут: он участвовал в институтской художественной самодеятельности, посвящая этому все свободное, да и не очень свободное время.
В 1972 г. в Сыктывкаре проводился республиканский фестиваль-конкурс «Мы ищем таланты». Валера на нем победил и получил право учиться во Всесоюзной творческой мастерской эстрадного искусства. Он бросил институт и вновь отправился в Москву постигать тайны мастерства под руководством Г. П. Виноградова. Кстати, буквально накануне конкурса он, играя в спектакле народного театра, неудачно прыгнул и сломал пяточную кость: «Так что пред очи жюри я предстал в гипсе по колено и с клюкой в руках. До сих пор ломаю голову, что на них тогда произвело большее впечатление – мои вокальные данные или столь экзотический вид».
Правда, учеба продолжалась недолго: уже год спустя директор Сыктывкарской филармонии во время очередного посещения мастерской остался крайне недоволен результатами обучения и увез группу домой – работать. Вот так недоученный Леонтьев стал профессиональным артистом эстрады и начал выступать в компании таких же молодых энтузиастов – участников ансамбля «Мечтатели». До сих пор он помнит свой первый «профессиональный» концерт в сельском клубе деревни Лойма Коми АССР: «На улице было -38 °C. Примерно столько же – в здании. Мы нашли лопату, раскопали сугроб, извлекли из него дрова, скололи с них лед, заложили в печку, плеснули бензина из бензобака автобуса и спустя несколько часов смогли снять верхнюю одежду. В назначенное время пришли и сели на лавки все 40 зрителей. Сначала согрелись их тела, а по ходу концерта и души». Этот довольно далекий во времени эпизод сегодня гораздо крепче сидит в памяти Леонтьева, чем благополучное, осыпанное цветами и аплодисментами недавнее выступление в знаменитом нью-йоркском «Радио-Сити».