После окончания школы Расторгуев по настоянию родителей поступил в Московский технологический институт легкой промышленности. Однако вскоре выяснилось, что к учебе душа у него не лежит, и начались систематические прогулы занятий. То захочется пивка с друзьми попить, то в кино сходить. Однако староста в расторгуевской группе попался принципиальный, и на стол декану одна за другой ложились его докладные о нерадивых учениках. Но до поры до времени на них смотрели сквозь пальцы — думали, что прогульщики рано или поздно одумаются. Между тем судьбу Расторгуева решил один случай, который произошел в 1975 году, сразу после того, как группу прогульщиков лишили стипендии. Расторгуев надумал поговорить со старостой «по-мужски», но не рассчитал свои силы, и в итоге староста оказался в больнице. Естественно, дело дошло до руководства вуза, которое заняло жесткую позицию — Русторгуеву сначала влепили строгача, а затем завалили на сессии и отчислили. Так с мечтой о высшем образовании для своего отпрыска родителям Николая пришлось расстаться. Он же устроился слесарем в Центральный институт авиационного моторостроения. В 1976 году, в возрасте 19 лет, Расторгуев женился на девушке, которая жила с ним в одном дворе. Она была на год его моложе. Через год на свет появился мальчик, которого назвали Павлом.
Все свободное от работы время Расторгуев посвящал музыке. Его восхождение к славе началось с самых низов: сначала танцевальные площадки, затем — ресторан. В 1978 году уже набравшийся опыта гитарист и вокалист обратил на себя внимание известного музыканта-джазмена, саксофониста Виталия Клейнота. Тот был руководителем вокально-инструментального ансамбля «Шестеро молодых» и подыскивал в коллектив музыкантов, не испорченных советской эстрадой. Под это определение попал и Расторгуев.
В самом начале 80-х Расторгуев ушел из «Шестерки» и стал солистом популярного ВИА «Лейся, песня». Шлягер «Обручальное кольцо» в его исполнении распевала в те годы буквально вся страна (автору этих строк песня памятна тем, что под нее он с сослуживцами регулярно отжимался на плацу в переяславль-залесской учебке). Однако в 1985 году, несмотря на большую популярность этого ансамбля в народе, художественный совет не утвердил их очередную программу. Расторгуев вспоминает: «Каких только маразмов тогда не было! Одна сдача программы чего стоила! Всех заставляли петь одну и ту же песню. Сидела комиссия идиотов и решала, кого ставить, кого нет. Какой-то бывший баянист, ставший чиновником, тупо слушал и выносил свой вердикт. Мы сдавали программу вместе с Сашей Барыкиным. Характерно, что не сдал ни я, ни он. Как же мы ругались за кулисами на этих долболобых! В запале обсуждали даже, не нанять ли человека, чтобы пристрелить кого-нибудь из них…»
После распада «Шестерки» Расторгуев попал в группу «Рондо», но его пребывание в ней закончилось довольно скоро. Группа отправилась на Сахалин, чтобы устроиться на работу в местную филармонию. Однако музыканты просидели там месяц, подготовили программу, а ее не приняли. Причем предъявлять претензии было некому — не бывшему же часовых дел мастеру, а ныне художественному руководителю филармонии, или директору — одному из бывших замов местного обкома партии, курировавшему сельское хозяйство.
После «Рондо» Расторгуев некоторое время сидел без работы. Чуть ли не ежедневно он ходил на прослушивания в самые различные музыкальные коллективы, но его никуда не брали. То ли голосом не вышел, то ли внешностью. И вот однажды известный ныне музыкант из «Морального кодекса» Сергей Мазаев посоветовал Расторгуеву попытать счастья в ансамбле «Здравствуй, песня!», художественным руководителем которого был Игорь Матвиенко. Расторгуеву терять было нечего, он пришел… и тут же был взят в качестве солиста.
Н. Расторгуев вспоминает: «Спиртное я поначалу не употреблял. А потом, когда уже заматерел, иногда позволял себе с ребятами выпить перед концертом. Не так, чтоб уж очень, но было… У меня достаточно крепкий организм, могу выдерживать серьезные нагрузки. Помню, поехали на БАМ, когда там был «сухой закон». Мы купили огромный чемодан, набили его водкой и выпили ее за два дня впятером. Вообще-то мы вели концерты сами, конферансье не было. И все было чин чинарем. Однажды выпили крепко, и у меня язык стал заплетаться. Вроде все поется, а слова не выговариваются. Народ начал смеяться. С того момента сам себе дал слово — ни грамма перед выступлением…»
После «Здравствуй, песня!» Расторгуев работал еще в нескольких коллективах (например, в группе Вячеслава Добрынина), после чего его пути-дороги вновь пересеклись с Игорем Матвиенко. В 1988 году тот вместе с поэтом Александром Шагановым задумал создать группу «Любэ» и в качестве вокалиста пригласил именно Расторгуева. Певец вспоминает: