Однако это не отпугнуло от молодого актера других режиссеров. В итоге два режиссера с той же киевской киностудии — Александр Алов и Владимир Наумов — в 1954 году пригласили Рыбникова в свой фильм «Тревожная молодость». В этой картине актеру досталась роль сугубо отрицательная, но одна из центральных — Котьки Григоренко.

Премьера фильма состоялась 29 апреля 1955 года и была очень хорошо встречена зрителем. По сути, именно с этого фильма началась звездная судьба режиссерского тандема Алов — Наумов, а также трех актеров, которые исполняли в нем главные роли: Николая Рыбникова, Александра Суснина и Тамары Логиновой. Эти трое стали настоящими звездами советского кино 50-х годов.

На момент выхода «Тревожной молодости» Рыбников уже снимался в новом фильме. Это была мелодрама о деревенской жизни с социальным уклоном — «Чужая родня» Михаила Швейцера. Этот фильм вышел на широкий экран в январе 1956 года и, конечно, прибавил новую толику славы Николаю Рыбникову. Но именно, что толику, поскольку настоящий обвал популярности у этого актера произошел спустя десять месяцев, а именно — 26 ноября 1956 года, когда в прокат была выпущена мелодрама «Весна на Заречной улице» Феликса Миронера и Марлена Хуциева, где Рыбников вновь сыграл главную роль — уже не колхозника, а сталевара Сашу Савченко.

По сюжету, у Савченко есть любимая девушка Зина, которая любит его и готова выйти замуж хоть завтра — только позови. Но тут в вечернюю школу рабочей молодежи приходит новая молодая учительница Татьяна Сергеевна Левченко, и у героя Рыбникова от любви к ней буквально меркнет сознание. Эта любовь и стала главным лейтмотивом всего фильма.

Итак, в «Весне на Заречной улице» (фильм собрал в прокате 30, 12 млн. зрителей, 9-е место) Рыбников исполнил роль простого рабочего парня, металлурга. Скажем прямо, до этого в советском кино многие актеры играли роли рабочих парней. Однако это были несколько иные герои: слишком пафосные, слишком правильные. С приходом в кино такого актера, как Рыбников (а также Алексей Баталов), эти роли обрели иную окраску: более простую и человечную. Вот и Рыбников сыграл своего металлурга Сашу Савченко настолько обаятельно, что буквально влюбил в себя миллионы советских людей, которым пришлась по душе не только его актерская игра, но и талант певца (в фильме он исполнил песню «Когда весна придет», мгновенно ставшую всенародным шлягером). Как напишет позднее кинокритик Е. Третьяк:

«Вся страна запела песни, услышанные из уст рыбниковских героев про „заводскую проходную, что в люди вывела меня“ и „не кочегары мы, не плотники“…

В своих героях — молодых рабочих парнях — Николай Рыбников сумел передать то главное, чем жила в те дни страна. Они были не просто узнаваемы современниками, они выражали нерв времени, его проблемы, его стремления. Им верили, на них хотели походить…»

Буквально спустя несколько месяцев — 29 апреля 1957 года — на широкий экран вышел еще один шедевр с участием актера — фильм «Высота» Александра Зархи, где Рыбников сыграл еще одного рабочего парня — на этот раз высотника-монтажника Николая Пасечника. И в этом фильме Рыбников исполнил песню, которую запела вся страна: «Не кочегары мы, не плотники».

В прокате 1957 года фильм «Высота» занял 17-е место, собрав 24, 8 млн. зрителей.

Именно во время съемок фильма «Высота» круто изменилась личная жизнь Рыбникова — он наконец женился на своей бывшей однокурснице по ВГИКу Алле Ларионовой. Хотя путь к этой свадьбе был для них долог и тернист.

Как мы помним, в первой половине 50-х Ларионова крутила роман с известным артистом Михаилом Кузнецовым. Но эти отношения в итоге были прерваны по желанию актера — его жена была серьезно больна, поэтому он не хотел доставлять ей лишние страдания. В итоге очень скоро возле Ларионовой появился новый воздыхатель, причем опять именитый. Это был популярный актер Иван Переверзев, который был старше ее почти на 18 лет.

Как и Кузнецов, Переверзев на тот момент тоже был несвободен — он вновь пытался воссоединиться со своей бывшей женой актрисой Надеждой Чередниченко. А также крутил роман еще с одной актрисой — Кирой Канаевой. Вот здесь ему на пути и повстречалась Ларионова, с которой он летом 1956 года должен был сниматься в одном фильме — «Полесская легенда» (они играли главные роли — возлюбленных). Но накануне съемок судьба свела их в совместной творческой поездке в Ленинград, где они должны были выступать в сборном концерте. Ларионова поехала туда одна, а Переверзев — в компании с Чередниченко. Что было дальше, последняя рассказывает следующее:

«Мы с Переверзевым ехали в одном купе. Иван вышел с Владимиром Дружниковым в тамбур покурить. По дороге встретили Ларионову, пошли в ресторан попить пивка. Переверзев меня предупредил: „Я ненадолго“. В ресторане сидели до утра, все были в стельку. Когда Иван выходил из поезда, то даже не зашел в наше купе — выносил чемоданы Ларионовой.

Нас всех поселили в гостинице „Европейская“. Их рядом на верхнем этаже, меня на нижнем. В концертной программе меня поставили первой, а их последними, чтобы мы не встречались. Я ужасно переживала, готова была умереть. Пела с трудом. Иван боялся показаться мне на глаза. А из Ленинграда вместе с Ларионовой уехал в Белоруссию на съемки „Полесской легенды“. Переверзев позвонил режиссеру и потребовал, чтобы на место утвержденной актрисы взяли Ларионову, иначе, мол, он сниматься не будет. И парочка укатила… Там Алла и забеременела, думала, что уж теперь точно женит Ивана на себе. Но когда он увидел, что живот растет, то стал думать, как от нее сбежать.

И вот представьте себе положение. Канаева на сохранении (от того же Переверзева) в больнице лежит, вот-вот родит. Ларионова на восьмом месяце. Иван пришел ко мне, умолял принять обратно. И я приняла. Даже не знаю, что со мной случилось. Злоба какая-то появилась на все это…»

Рыбников в это время находился в Ялте на съемках фильма «Высота» и, узнав о новом серьезном увлечении Ларионовой, впал в депрессию: закрылся в своем гостиничном номере и запил. Вот как об этом вспоминает очевидец тех событий режиссер Эмма Дукельская:

«Как-то пришли ко мне встревоженные актеры и сказали, что Рыбников заперся в своем номере, пьет, на стук в дверь не отвечает и никого к себе не пускает. Переживает, видно. Тогда-то я и узнала о его любви к Алле Ларионовой и поразилась: ведь сколько времени мы проводили вместе, о чем только не беседовали, а об этой своей главной боли он молчал! Николай не был „распахнутым“ человеком. Ребята сказали, что надо что-то делать, что опасно оставлять его в таком состоянии одного, что с его взрывным характером он способен на любую крайность…

Я помчалась к нему. На мой стук он откликнулся, но, как я ни просила, двери не открыл. Я говорила ему какие-то слова, предлагала еду, призывала к здравому смыслу… Много времени прошло, пока он наконец появился на пороге…»

Как ни странно, но справиться с депрессией Рыбникову помог… сам Переверзев. Когда в июне 56-го он узнал, что Ларионова от него забеременела, то стал настаивать на аборте. Но Алла не согласилась — это была ее первая беременность. Тогда Переверзев собрал вещи и уехал в Москву. Ларионова оказалась в отчаянном положении, но тут ей на помощь пришел Рыбников. Узнав о том, что случилось с Аллой, он немедленно вылетел к ней в Минск, даже не предупредив съемочную группу. На календаре был канун 1957 года. В первый же рабочий день после праздника — 2 января — Рыбников повел Ларионову в ЗАГС. Как признается много позже сама актриса, за Николая она тогда выходила от отчаяния. А все мысли ее всегда были лишь о первой любви — о Вадиме Захарченко. Если бы это он объявился тогда в Минске, она за ним хоть босиком пошла бы. Но у Захарченко тогда была уже другая женщина (он познакомился с ней на съемках фильма «Тихий Дон»).