Рыбников приехал в Минск к Ларионовой (она снималась в фильме "Полесская легенда") в канун Нового, 1957 года. В первый же рабочий день после праздника — 2 января — они отправились в загс. Как вспоминает сама актриса: "На премьере «Высоты» в Доме кино мы уже сидели рядом. И когда герой фильма, которого тоже звали Николаем, произнес с экрана: "Эх, прощай, Коля, твоя холостая жизнь!" — зал взорвался аплодисментами".
В 1961 году у Рыбникова и Ларионовой родилась дочь, которую назвали Арина. В связи с этим Алла Ларионова вспоминает: "То, что я решилась иметь двоих детей, в актерской среде считалось едва ли не подвигом. Правда, если бы не моя мама, не знаю, как бы мы справились… Но я очень рада, что они у меня есть. Многие актрисы ведь так и не собрались родить — боялись, что это помешает карьере, испортит фигуру".
В 1957 году Рыбников впервые попробовал себя в комедии, снявшись в фильме Э. Рязанова "Девушка без адреса". Фильм имел огромный успех у публики: в 1958 году он занял 2-е место в прокате, собрав 36,5 млн. зрителей. Такого успеха больше не знал ни один фильм с участием Рыбникова. Однако критика, да и сам режиссер Э. Рязанов, посчитали эту картину малоудачной, а роль Николая Рыбникова в ней провальной.
Между тем, помимо кино, Рыбников играл и на сцене Театра киноактера, однако, видимо, эта деятельность его привлекала меньше, чем работа в кинематографе. В конце 50-х актера даже отчислили из труппы за пьянство (после того, как он вместе с С. Гурзо сорвал очередной спектакль). Однако через некоторое время Рыбникова вновь зачислили в штат театра, видимо, учитывая его огромную популярность среди зрителей.
В те же годы Рыбников в составе небольшой делегации, состоящей из кинематографических семей (Рыбников — Ларионова, Бондарчук — Скобцева, Тихонов — Мордюкова), попал на встречу с Н. С. Хрущевым. Встреча проходила в подмосковном местечке Архангельское, на природе. Программа этого мероприятия была довольно насыщенной и включала в себя массу мероприятий рыбалку, концерт, плавание в местном озере, обед. В конце встречи состоялась беседа Хрущева с многочисленными гостями. Во время этой беседы Рыбников внезапно потерял всякое чувство осторожности и, когда Хрущев вышел к микрофону и начал говорить, внезапно прервал его на полуслове и попросил: "Никита Сергеевич, расскажите лучше про Кубу!" Не привыкший к тому, чтобы его обрывали, Хрущев весь позеленел и гневно произнес: "Газеты надо читать, там все написано!"
После этого инцидента пребывание актерской делегации на встрече продлилось совсем недолго. Вскоре к их столу подошел суровый человек в штатском и спросил: "Вы, наверное, домой хотите?" И первым за всех ответил Рыбников: «Хотим». Им подали машину, и они спешно ретировались из Архангельского. Стоит отметить, что даже в такой ситуации Рыбников не утратил своего природного оптимизма и напоследок прихватил с собой мешок с раками.
К счастью, этот инцидент не повлек за собой никаких оргвыводов, и Рыбникову об этом сообщила сама министр культуры Фурцева. Она позвонила ему домой и радостно оповестила: "Николай Николаевич, можете не волноваться, все обошлось. Никита Сергеевич не сердится…
Между тем в 1961 году Рыбников вновь решил попробовать свои силы в комедии и принял предложение режиссера Юрия Чулюкина сняться в фильме «Девчата». По словам других участников съемок, Рыбников поначалу с прохладцей относился к работе над этой картиной, считая ее драматургию откровенно слабой. Однако постепенно свое мнение к фильму он изменил. Решающим фактором при этом стало мнение мэтра режиссуры Михаила Ромма, который прочитал сценарий и похвалил его. После этого Рыбников начал активно участвовать в съемках фильма.
Когда картина вышла на экран, ее успех был огромным (в прокате картина взяла 5-е место — 34,8 млн. зрителей). Однако критика вновь принялась выискивать огрехи в работе актера. Например, С. Розен писал: "Мне было бы очень жаль, если бы Рыбников посчитал свою работу над образом Ильи Ковригина в «Девчатах» шагом вперед.
После "Девушки без адреса" прошло четыре года. Актер опять встретился с комедийным жанром, но на сей раз потерпел поражение потому, что сам связал себе руки…
Между тем роль в «Девчатах» оказалась для Рыбникова последней успешной ролью в том десятилетии. Несмотря на то, что в последующие девять лет он снялся в десяти картинах, ни одна из них не принесла ему столь шумного успеха, как роль Ильи Ковригина. В каких же фильмах увидели тогда зрители Рыбникова? "Им покоряется небо" (1963), «Хоккеисты» (1964), "Война и мир" (1965 — 1967), "Дядюшкин сон" (1967), "Разбудите Мухина", т/ф "Длинный день Кольки Павлюкова" (оба — 1968), т/ф "Люди, как реки" (1969), "Старый знакомый", "Плечом к плечу", «Освобождение» (все — 1970).
Из этого списка наиболее популярными у зрителей оказались три работы Рыбникова — речь идет о фильмах: "Им покоряется небо", «Хоккеисты» и "Война и мир".
В первой картине (режиссер Татьяна Лиознова) актер сыграл летчика-испытателя Алексея Колчина, который погибает во время испытания реактивного самолета. Кстати, это одна из редких работ актера, в которой герой, сыгранный им, погибает.
В фильме режиссера Рафаила Гольдина «Хоккеисты» Рыбников играет тренера Лашкова. Стоит отметить, что актер очень любил хоккей и частенько в свободное время вставал на коньки и брал в руки клюшку. (Чего не скажешь об исполнителе главной роли актере В. Шалевиче, который кататься на коньках не умел, поэтому на съемках его заменял дублер.) Болел Рыбников за ЦСКА, где у него было много друзей, но самым близким был прославленный форвард Всеволод Бобров.
И, наконец, в эпопее С. Бондарчука "Война и мир" Рыбников сыграл гусара и поэта Дениса Давыдова. Нечто подобное актер уже играл в фильме «Кочубей» (1959), где ему также пришлось скакать на лошади, стрелять и фехтовать саблей.
Любопытный эпизод произошел с Рыбниковым и Ларионовой во время их совместной работы в картине "Длинный день Кольки Павлюкова". Рассказывает Алла Ларионова: "Коля был очень ревнивый. Собрались мы как-то у моей приятельницы, директора этой картины. Коля должен был подъехать чуть позже. Среди гостей был мальчик, мой поклонник. Вдруг оказывается, что он помнит наизусть буквально все мои реплики в фильмах, даже те, что я сама забыла. И вот в одной из комнат он встал передо мной на колени и начал повторять киноэпизод — "целый монолог дословно. В это время открывается дверь, входит Коля, дает ему по уху изо всей силы. Мальчик отлетает… Я, конечно: "Ты что, ты что!.. А он лишь развернулся, хлопнул дверью и ушел…
Помимо кино, имя Рыбникова прославилось в те годы еще в одной области — песенном творчестве. Дело в том, что в конце 60-х в обществе стали распространяться магнитофонные кассеты с записями песен под гитару в его исполнении. Причем среди этих песен были не только те, что он пел в фильмах, но и входившие в моду блатные песни (этим делом тогда «грешили» В. Высоцкий, М. Ножкин и другие драматические актеры). Популярность этих кассет была настолько огромной, что компетентные органы не могли не обратить внимания на этот факт. Сначала в центральной прессе появился фельетон, в котором довольно прозрачно намекалось на то, что "бывшие монтажники-высотники теперь поют антисоветские песни". Затем, когда в руки КГБ попала очередная кассета с записью песен, якобы в исполнении артиста, Рыбникова вызвали на Лубянку. Дали прослушать запись. "Это вы поете?" спросили строго. "Нет, не я", — "ответил артист. Тогда была проведена тщательная экспертиза этой записи. К удивлению чекистов, экспертиза установила, что актер действительно не имеет ни малейшего отношения к этой записи и что это ловкая имитация голоса Рыбникова кем-то из доморощенных подпольных певцов.