В 1971 году филармония объявила конкурс самодеятельных артистов с тем, чтобы наиболее толковых отправить учиться в столицу. Конкурсный отбор проводила высокая комиссия из Москвы. И надо было такому случиться, что накануне конкурса Леонтьев был занят в спектакле местного театра «Затюканный апостол» и умудрился сломать ногу. Ситуация сложилась крайне неприятная, но не в характере Леонтьева было опускать раньше времени руки. В итоге даже гипс не сумел сдержать его энергии, и экзаменаторы были несказанно удивлены талантами 24-летнего певца. Так Леонтьев, в числе 14 других счастливчиков, оказался во Всесоюзной мастерской циркового и эстрадного искусства, на курсе знаменитого певца Г. П. Виноградова.
В 1973 году Леонтьев закончил мастерскую и вернулся в Сыктывкар. Там его уже ждал инструментальный ансамбль «Эхо», готовый к предстоящей гастрольно-концертной деятельности. Организовала коллектив выпускница Сыктывкарского музыкального училища Людмила Исакович, которая вскоре стала женой Леонтьева. С этим коллективом они объездили почти весь Союз, в основном выступая в провинции. Во время одного из таких выступлений Леонтьев познакомился с руководителем популярного ансамбля «Интеграл» Бари Алибасовым, и тот пригласил талантливого певца к себе в коллектив. Однако Леонтьев по ряду причин отказался от этого предложения и продолжил свою сольную карьеру в составе родного «Эха».
В 1979 году Леонтьев покинул Сыктывкар и перебрался сначала в Горький, а затем в Луганск, став солистом Ворошиловградской филармонии. Именно от нее он и отправился в том же году на международный фестиваль «Ялта-79», где неожиданно Для себя стал лауреатом, исполнив песню Давида Тухманова «Памяти гитариста». Однако радость этого события омрачила трагедия - в день объявления победителей умер отец Леонтьева, так и не узнав о победе сына.
Знакомство с Тухмановым, который в те годы считался одним из самых популярных композиторов на советской эстраде, круто изменило судьбу Леонтьева. Оно открыло некогда безвестному певцу двери в эстрадную тусовку, пополнило его репертуар целым рядом шлягеров («Там в сентябре», «Бреду по желтым склонам», «Ненаглядная сторона»), позволило ему выступить на ряде престижных конкурсов и завоевать на них несколько наград. Среди них: «Гран-при» на фестивале песни «Золотой Орфей» в Болгарии в 1980 году, «Приз популярности» на музыкальном фестивале «Ереван-81».
Однако необычный сценический облик Леонтьева, его экспрессивная манера исполнения и голос, который не вписывался в привычные рамки, вызывали жгучее неприятие у руководителей советской эстрады. Поэтому несмотря на то, что имя Леонтьева уже становилось известным среди слушателей, мысли о том, чтобы расширять его популярность посредством телевидения, у высокого руководства даже не возникало. Показав Леонтьева всего один раз по ЦТ с песней «Ненаглядная сторона» (при этом певцу приказали стоять перед камерой чуть ли не по стойке «смирно»), чиновники затем перестали пускать его на голубой экран. Почему? Говорят, что чашу терпения чиновников переполнил случай, произошедший сразу после выступления Леонтьева на фестивале «Ереван-81». Аккредитованные на фестивале американские журналисты имели смелость сравнить вокал Леонтьева с Миком Джаггером, а хореографию с Михаилом Барышниковым, написали об этом в своем журнале, и тот какими-то неведомыми путями лег на стол бывшего председателя Гостелерадио СССР. Лапин возмутился (мол, наш советский певец копирует западных кумиров) и запретил показывать Леонтьева по телевидению. В том же году с Лапиным солидаризировались и чиновники из Министерства культуры, которые внесли певца в «черный список» артистов, которым было запрещено выступать в крупных городах, таких, как Москва, Киев, Ялта и др.
Между тем, несмотря на активное сопротивление официальных властей, популярность Леонтьева среди простых слушателей в начале 80-х была чрезвычайно высокой. В те годы даже кинематографисты обратили внимание на талантливого певца - режиссер Владимир Лаптев пригласил его на небольшую роль в свою картину «На чужом празднике» (1981). На концертах Леонтьева всегда были аншлаги, а в эстрадной среде появились поклонницы, которые именовали себя «фанатками Леонтьева». Они преследовали своего кумира буквально повсюду. Например, когда он жил в Москве, то всегда останавливался на квартире у друга на Каляевской улице. А окна ванной комнаты у того выходили на черный ход. Однако, несмотря на то что окно закрыли металлическим щитом, вездесущие фанатки умудрились просверлить в нем дырочку и подглядывали за моющимся Леонтьевым. То же самое было и в спальне - это был последний этаж, и фанатки проделали отверстие в потолке и ежедневно «прилипали» к нему с тайной надеждой увидеть что-нибудь «экзотическое». Их удалось разоблачить только после того, как однажды вечером на кровать певца рухнула штукатурка. К счастью, его самого в тот момент в комнате не оказалось.
Однако это было еще не все, на что были способны фанатки Леонтьева. В другом случае ему, например, пришлось давать объяснения в милиции по поводу самоубийства одной из своих поклонниц. Дело было так.
В начале 80-х Леонтьев работал в популярной программе «Мелодии друзей» (в ней вместе с советскими исполнителями участвовали и артисты из социалистических стран) и жил в гостинице «Украина». Однажды после концерта он сидел в номере польской певицы Марыли Родович, когда за ним пришли люди в штатском. «Валерий Яковлевич, просим вас следовать за нами», - обратились они к певцу и сопроводили его в служебный кабинет гостиницы. Там выяснилось, что одна из поклонниц певца, закрывшись в туалете, отравилась йодом. При этом на месте происшествия она оставила записку: «В моей смерти прошу винить Валерия Леонтьева». Нетрудно себе представить, какие чувства испытал при этом известии певец и каких трудов ему стоило убедить людей в штатском поверить в то, что он никогда не был знаком с самоубийцей. К счастью, девушку удалось спасти и эту историю замяли.
Еще одна история, связанная с поклонницами певца, произошла примерно в то же время, что и первая. Некая девица пришла к Леонтьеву за кулисы и, представившись журналисткой газеты «Советская культура», попросила дать ей интервью. Так как вниманием прессы Леонтьев в те годы избалован не был, он с Удовольствием согласился. И вот в назначенный час он накрыл у себя в гримерке скромный стол с шампанским и бисквитами, купил цветы. Вскоре явилась гостья, и беседа началась. Длилась она около двух часов и прошла, как говорится, «в теплой и дружеской обстановке». Когда все вопросы были исчерпаны и собеседники стали прощаться, Леонтьев попросил девушку оставить свой домашний телефон. Та что-то написала на листочке, сложила его и отдала певцу. Когда через некоторое время певец заглянул в бумажку, он вместо семизначного номера прочел короткую фразу: «Это была шутка...»
