Начались бесконечные гастроли, но о чем еще может мечтать молодой парень, увлеченный своей профессией, как не об этом? В 1975 г. Валерий стал солистом ансамбля республиканской филармонии «Эхо», с которым он ездит до сих пор. Коллективом руководила выпускница Сыктывкарского музыкального училища Людмила Исакович, с которой Леонтьев познакомился еще в 1972 г. Тогда она играла на бас-гитаре и воплощала на сцене образ «советской Сюзи Кватро». Спустя несколько лет молодые люди поженились: регистрация произошла на гастролях в Магадане, что называется «в рабочем порядке».
В 1978 г. Валерий вместе с «Эхом» перешел в Горьковскую филармонию. А в августе того же года принял участие в I Всесоюзном конкурсе на лучшее исполнение песен соцстран в Ялте, где получил 1-ю премию по разделу сольного пения. Зимой следующего года состоялось знакомство с Давидом Тухмановым, которое было вызвано головокружительным успехом Леонтьева в Ялте. Сам композитор вспоминал: «Я не увидел в нем певца универсального, сочетающего вокальные, актерские и пластические возможности, которые впоследствии так ярко раскрылись на сцене. Я не почувствовал в нем личности энергичной, упорной, настойчивой и работоспособной, не ощутил тогда его одухотворенности, чуткости, что проявилось впоследствии в совместной работе. Но я заметил главное: музыкальность, хорошие певческие данные, техничность, свободное владение современными исполнительскими приемами». И началась работа. Работа, которая продолжалась не один год и подарила публике целую россыпь замечательных песен.
Однако чиновников от искусства талантливый певец раздражал, и они делали все, чтобы не показывать его «широким массам». Однажды он снялся в новогоднем «Голубом огоньке» с песней Тухманова «Кружатся диски». В день эфира сел с друзьями у телевизора – смотреть: «Без десяти полночь звонит жена Тухманова Татьяна и сообщает, что меня в “Огоньке” не будет. В другой раз в “Огоньке” снимался с песней “Ненаглядная сторона”. Так чтоб я в своей манере на сцене не крутился, заставили встать на стул, на котором я и простоял весь номер. О костюмах вообще молчу…»
Летом 1980 г. на Международном фестивале эстрадной песни «Золотой Орфей» Леонтьев получил 1-ю премию и специальный приз болгарского журнала мод «Лада» за лучшие сценические костюмы (которые он, кстати, придумывал и шил сам). С этого момента казалось, что началось стремительное восхождение Валерия на эстрадный Олимп. Первыми были концерты в московских ДК, потом Театр эстрады, Лужники, «Октябрьский». На конкурсе-фестивале популярной советской песни «Ереван-81» молодой певец Леонтьев получил приз публики и газеты «Вечерний Ереван».
Тогда же американский журнал «Тайм» посвятил ни с того ни с сего две страницы этому фестивалю и опубликовал портрет Валерия с восторженным комментарием, в котором его сравнивали с Миком Джаггером и Михаилом Барышниковым: «Советская-то пресса тогда молчала… Для того времени это было круто. Все равно что с Гитлером бы сравнили или еще хуже – с Троцким каким-нибудь… “Доброжелатели” подложили этот журнал председателю Гостелерадио СССР Лапину, после чего за эти сравнения я долго расплачивался: эфир для меня закрылся на многие годы…»
Зато в это время Валерий познакомился с Раймондом Паулсом и Лорой Квинт – людьми, оказавшими сильное влияние на его творчество. Но тогда же будущая исполнительская карьера певца оказалась под вопросом: в 1982 г. хирург Ральф Райкин (брат Аркадия) удалил ему из горла опухоль. Тогда Леонтьев задумался о высшем образовании, которого так и не имел, и поступил в Институт культуры им. Крупской на специальность «режиссер массовых представлений». К счастью, оказалось, что петь Валерий сможет, уже в следующем году он дал в городе на Неве 18 аншлаговых концертов с новой программой «Я просто певец», но учебу не бросил.
В 1983 г. Леонтьев перешел в Ворошиловградскую филармонию и через два года получил свою первую крупную награду – премию Ленинского комсомола, что было официальным признанием его властями. Теперь он участвовал во всевозможных творческих вечерах (иногда даже в Москве). Почти каждый год выходил в свет, по крайней мере, один новый альбом певца.
В конце 1980-х гг. он приобрел себе квартиру в столице около Белорусского вокзала: «Разумеется, дома были самые что ни на есть обычные – ни о какой охране в подъездах даже речь в то время не шла. Это была не жизнь, а сущий ад. Соседи ненавидели меня и мечтали о том дне, когда меня переедет трамвай или, быть может, я найду квартиру получше и перееду в другой дом. Подъезд был загажен до неузнаваемости. В 4–5 часов утра, в любое время суток мою дверь пинали ногами люди, которые заявились прямиком с вокзала. Узнав от кого-то, что в этом доме живет Леонтьев, они спешили удостовериться. Я, уже заработавший на этом невроз, кричал: “Кто?”, а в ответ из-за двери раздавалось: “Открой, поглядеть хотим!”»