В конце октября Агутин демобилизовался и вернулся в Москву. А уже через два дня после возвращения возобновил прерванную два года назад учебу в институте культуры. Причем днем он интенсивно учился, а ночью, столь же яростно, писал песни. Однако на то, что ему когда-нибудь удастся их куда-нибудь пристроить, не было надежды даже у самых близких ему людей. Например, его отец однажды так и заявил: «Пробивайся сам. Я вряд ли смогу тебе помочь». Помогла же Агутину чистая случайность. Однажды его матери позвонила знакомая, которая летом ездила работать с артистами. После этой поездки в ее записной книжке появился телефон одного певца, знакомый звукорежиссер которого работал на студии. Именно к нему и было предложено обратиться Агутину. Он так и поступил. Позвонил звукорежиссеру и выяснил, что запись одной песни обойдется ему в 360 рублей. Радости Агутина и его матери не было предела. До этого им кто-то сказал, что такая запись стоит тысячу рублей. Учитывая, что мать Леонида получала на работе 180 рублей, а сам Агутин вообще не имел за душой ни копейки, такая сумма была для них чем-то заоблачным. А тут всего 360 рублей! Короче, такие деньги они нашли, и вскоре Агутин записал в студии свою первую песню — «Морской этюд». А недели через две удалось записать еще две песни (деньги на одну из них дал отец Леонида). Во время записи третьей песни звукорежиссер внезапно признался Агутину, что его песни ему нравятся и он постарается пробить их на радио. И ведь пробил! В октябре 1989 года в одном из выпусков передачи «С добрым утром!» прозвучала песня Агутина «Морской этюд».
Однако чтобы заявить о себе в полный голос, одного выхода на радио было недостаточно. А на широкую раскрутку денег у Агутина не было. Поэтому последующие несколько лет он посвятил накоплению средств и необходимых связей в музыкальном мире. Для этого ему пришлось участвовать в качестве рядового музыканта в записи и выступлениях более популярных артистов. Его мать, Людмила Леонидовна вспоминает: «Заработки, конечно, были небольшие, а хотелось и приодеться. Надо было видеть, в чем он ездил в институт на занятия зимой. Надевал старую дубленку отца с потертым воротником. А чтобы этого не было видно, он поднимал воротник и обматывал его несколько раз моим шерстяным шарфом. На голове шапка-пирожок, тоже оставленная отцом. Ленька отворачивал ее борта, и она становилась похожа на причудливую папаху.
Глядя на него, я и смеялась, и плакала. А он, как всегда, шутил:
— Нормально. Никто в таком «прикиде» не ходит. Мне нравится…»
В 1991 году Агутин окончил институт культуры по специальности «режиссер эстрадных театрализованных представлений». Однако работать по специальности он так и не устроился, предпочитая все свое время посвящать музыке. В те годы он уже успел несколько раз «засветиться» на голубых экранах с собственными песнями, правда, в передачах, считающихся не рейтинговыми (например, в передаче про рыболовов).
В 1992 году Агутин принял решение попытать счастья в конкурсе молодых исполнителей эстрадной песни, ежегодно проходившем в Ялте. На суд строгого жюри он вынес несколько песен, среди которых был и «Босоногий мальчик». Эта песня принесла ему 1-е место.
Л. Агутин вспоминает: «Я получил первую премию, несмотря на то что некоторые члены жюри были настроены очень сурово. Именно там я исполнил в первый раз песенку «Босоногий мальчик». Было жарко, и я вышел на сцену босиком и в шортах. И, видно, так вошел в роль, что название стало моим прозвищем — наверное, все решили, что песня обо мне…»
Ровно через год — летом 1993-го — Агутин стал участником еще одного престижного музыкального конкурса — «Юрмала-93». И здесь его сценический «прикид» был соответствующий: шорты, футболка, расстегнутая рубашка навыпуск, с болтающейся карточкой участника фестиваля, широкая лента через лоб и темные очки. Агутин вновь пел «Босоногого мальчика», ряд других песен. Только на этот раз он занял 3-е место. Но и этот результат можно было смело считать победой. Еще один успех его ждал по возвращении в Москву. В телепрограмме «Музыкальный экзамен» Агутину вручили хрустальный диск как лучшему композитору 1993 года.
25 января 1994 года в столичном ДК «Меридиан» состоялся первый сольный концерт Леонида Агутина. На концерте был аншлаг. Вот как описывает это событие Людмила Леонидовна: «Большинство песен исполнялось впервые. Публика вела себя очень свободно. Уже на пятой песне молодежь и дети начали танцевать в проходах и прямо перед сценой, громко выражая свои эмоции.
— Леня, это хит! — крикнул кто-то после окончившейся песни «Хоп-хэй-ла-ла-лэй…»
Зал подхватил и зааплодировал. Я хлопала и кричала вместе с ними, охваченная чувством восторга и радости.
После концерта зашла за кулисы. Пробиться сквозь толпу поклонников и поклонниц, желающих поздравить своего кумира, сфотографироваться с ним на память, было непросто…»
Именно с 1994 года имя Леонида Агутина стало широко известно в музыкальном мире. Тогда вышел его первый альбом «Босоногий мальчик», его выступления стали регулярно демонстрироваться в самых рейтинговых передачах как на ТВ («Утренняя почта», «Песня года» и т. д.), так и на радио.
В апреле 1995 года Агутин заключил свой первый спонсорский контракт — с российским представительством фирмы «Diesel». Затем подобные контракты пошли один за другим: с немецкой фирмой «Reemtsma» (сигареты «West»), с «Whiye Hall» (представляет в России коньяки «Henessy» и «Gautier»), с австрийской фирмой «BM Musik & Art». Последний контракт (заключен в декабре 1996 года) был особенным. Во-первых, он не спонсорский, а во-вторых — исключительно европейский. Его основная цель не просто представить российского певца на европейском рынке, но и сделать его популярным. Стоит отметить, что за право раскрутить Агутина бились сразу четыре менеджерских компании из Атланты (США), Финляндии, Франции и Австрии. Победили последние.
В 1995–1996 годах свет увидели еще два альбома Л. Агутина: «Декамерон» и «Летний дождь».
Сегодня Агутин уверенно входит в десятку самых раскрученных российских исполнителей. У него сотни тысяч поклонников по всей стране, его концерты проходят с неизменным аншлагом. Подтверждением этих слов стало последнее крупное выступление Агутина на фестивале «Славянский базар» летом 1998 года.
Несмотря на то что о своей личной жизни Агутин старается не распространяться, кое-какие сведения о ней периодически появляются в российской прессе. Например, известно, что в жизни Агутина было три настоящих любви. Одну женщину он любил восемь лет, другую — свою официальную жену Светлану — около пяти лет. С нею он расстался в 1993 году, в период работы над первым альбомом. Вскоре после развода у Агутина появилась новая пассия — балерина Большого театра Мария. Судьба свела их вместе в 1994 году в Париже, где Мария была на гастролях. Пообщавшись пару дней, молодые расстались, чтобы значительно позже встретиться вновь — на этот раз в Сочи. Агутин выступал с концертами, и Маша, находившаяся у моря на отдыхе, пришла на его концерт с цветами, которые и вручила своему кумиру за кулисами. Агутин тут же назначил ей свидание. В Москве эти встречи имели дальнейшее продолжение, причем довольно тесное. В итоге — в 1997 году на свет появилась очаровательная малютка, которую назвали Полиной. Однако и в этом случае официальной регистрации не последовало. Агутин снял для Марии и Полины квартиру в центре Москвы, где регулярно их навещает. На вопрос корреспондента газеты «СПИД-Инфо», почему он не живет с любимыми людьми вместе, певец ответил: «Легче любить ребенка, чем друг друга. На мой взгляд, чтобы жить вместе и выносить супруга каждый день, нужна поистине безумная любовь. У нас с Марией есть связующее звено — Полина. Без нее нам двоим скучно…