В конце октября Агутин демобилизовался и вернулся в Москву. А уже через два дня после возвращения возобновил прерванную два года назад учебу в институте культуры. Причем днем он интенсивно учился, а ночью, столь же яростно, писал песни. Однако на то, что ему когда-нибудь удастся их куда-нибудь пристроить, не было надежды даже у самых близких ему людей. Например, его отец однажды так и заявил: "Пробивайся сам. Я вряд ли смогу тебе помочь". Помогла же Агутину чистая случайность. Однажды его матери позвонила знакомая, которая летом ездила работать с артистами. После этой поездки в ее записной книжке появился телефон одного певца, знакомый звукорежиссер которого работал на студии. Именно к нему и было предложено обратиться Агутину. Он так и поступил. Позвонил звукорежиссеру и выяснил, что запись одной песни обойдется ему в 360 рублей. Радости Агутина и его матери не было предела. До этого им кто-то сказал, что такая запись стоит тысячу рублей. Учитывая, что мать Леонида получала на работе 180 рублей, а сам Агутин вообще не имел за душой ни копейки, такая сумма была для них чем-то заоблачным. А тут всего 360 рублей! Короче, такие деньги они нашли, и вскоре Агутин записал в студии свою первую песню - "Морской этюд". А недели через две удалось записать еще две песни (деньги на одну из них дал отец Леонида). Во время записи третьей песни звукорежиссер внезапно признался Агутину, что его песни ему нравятся и он постарается пробить их на радио. И ведь пробил! В октябре 1989 года в одном из выпусков передачи "С добрым утром!" прозвучала песня Агутина "Морской этюд".

Однако чтобы заявить о себе в полный голос, одного выхода на радио было недостаточно. А на широкую раскрутку денег у Агутина не было. Поэтому последующие несколько лет он посвятил накоплению средств и необходимых связей в музыкальном мире. Для этого ему пришлось участвовать в качестве рядового музыканта в записи и выступлениях более популярных артистов. Его мать, Людмила Леонидовна вспоминает: "Заработки, конечно, были небольшие, а хотелось и приодеться. Надо было видеть, в чем он ездил в институт на занятия зимой. Надевал старую дубленку отца с потертым воротником. А чтобы этого не было видно, он поднимал воротник и обматывал его несколько раз моим шерстяным шарфом. На голове шапка-пирожок, тоже оставленная отцом. Ленька отворачивал ее борта, и она становилась похожа на причудливую папаху.

Глядя на него, я и смеялась, и плакала. А он, как всегда, шутил:

- Нормально. Никто в таком "прикиде" не ходит. Мне нравится..."

В 1991 году Агутин окончил институт культуры по специальности "режиссер эстрадных театрализованных представлений". Однако работать по специальности он так и не устроился, предпочитая все свое время посвящать музыке. В те годы он уже успел несколько раз "засветиться" на голубых экранах с собственными песнями, правда, в передачах, считающихся не рейтинговыми (например, в передаче про рыболовов).

В 1992 году Агутин принял решение попытать счастья в конкурсе молодых исполнителей эстрадной песни, ежегодно проходившем в Ялте. На суд строгого жюри он вынес несколько песен, среди которых был и "Босоногий мальчик". Эта песня принесла ему 1-е место.

Л. Агутин вспоминает: "Я получил первую премию, несмотря на то что некоторые члены жюри были настроены очень сурово. Именно там я исполнил в первый раз песенку "Босоногий мальчик". Было жарко, и я вышел на сцену босиком и в шортах. И, видно, так вошел в роль, что название стало моим прозвищем - наверное, все решили, что песня обо мне..."

Ровно через год - летом 1993-го - Агутин стал участником еще одного престижного музыкального конкурса - "Юрмала-93". И здесь его сценический "прикид" был соответствующий: шорты, футболка, расстегнутая рубашка навыпуск, с болтающейся карточкой участника фестиваля, широкая лента через лоб и темные очки.