В свободное от учебы время Николаев сутки напролет играл в ресторанах — гитарой и клавишными он в совершенстве овладел еще в Южно-Сахалинске. Однако через это прошли многие музыканты и композиторы, судьба которых в дальнейшем сложилась печально — они так и не сумели поймать свою «птицу счастья». А Николаев сумел. Он рассказывает: «Однажды меня пригласили на съемки в студию Центрального телевидения. Вернее, пригласили не меня, а коллектив, в котором я работал, — группу артистов Московской областной филармонии. Вот тогда и произошла знаменательная для меня встреча. Съемки наши уже закончились, и мы заскочили в буфет глотнуть горячего чая на дорожку. За соседним столиком сидела Алла Пугачева. Я впервые видел ее так близко. А так как она мне очень нравилась как певица и как артистка, то я в прямом смысле слова глаз с нее не сводил.

И вдруг — даже теперь цепенею от ужаса, что решился на это, — встал, подошел и спросил:

— Не нужны ли вашему ансамблю музыканты?

— Нужны! А на чем ты играешь?

— Это смотря какие музыканты вам нужны.

Алла Борисовна рассмеялась и попросила меня зайти завтра.

На следующий день, прослушиваясь у Аллы Пугачевой, я изо всех сил старался ей понравиться. Хотя, как мне самому кажется, играл гораздо хуже своих возможностей. Но… судьба в образе Пугачевой надо мною сжалилась, и меня приняли в ансамбль…»

В течение года Николаев исправно играл в «Рецитале», после чего набрался храбрости предложить Пугачевой свои песни. Причем хотел показать целых шесть штук, но поэт Михаил Танич его уговорил ограничиться двумя: песней на стихи К. Ваншенкина о «летающих тарелках» и «Айсбергом» на стихи супруги Танича Юлии Козловой (последняя песня тогда же попала в репертуар Ольги Зарубиной и ее тогдашнего супруга Александра Выгузова (Малинина). Песни Николаева Пугачевой понравились, и в 1982 году она включила их в свой репертуар. Затем были и другие николаевские хиты: «Расскажите, птицы», «Паромщик», «Две звезды», «Невозможно стало жить без тебя» и другие. В 1984 году всенародным хитом стала николаевская песня «Комарово», которую исполнил актер Игорь Скляр, а через год — песня «Программа телепередач» в исполнении Александра Барыкина.

В период тесного сотрудничества Николаева и Пугачевой им не удалось избежать досужих разговоров о том, что их связывают куда более близкие отношения, чем творческие. Однако сами они и тогда, и впоследствии дружно открещивались от этих обвинений. А Пугачева даже рассказала душещипательную историю о том, как в Николаева влюбилась не она… а ее дочь Кристина. Вот ее собственные слова: «Николаев стал лучшим другом нашей семьи, и был такой момент, что моя Кристина по уши влюбилась в молодого красивого композитора. Я не знала, что и делать. И придумали мы с Игорем такой поворот — он пришел в гости со взрослой дочерью. Это произвело такое сильное впечатление, что три дня и три ночи Кристи плакала не переставая, но мы добились чего хотели — ее любовь остыла…»

В середине 80-х Николаев почувствовал в себе силы работать самостоятельно и решил покинуть коллектив Пугачевой. Его первый сольный выход произошел в «Утренней почте», где был показан клип на песню «Мельница». Как напишет позднее один из журналистов: «манерный, гнусоватый голос композитора с интонациями героя провинциальной оперетты не всем сразу пришелся по вкусу.