Первую серьезную роль в кино Кустинская сыграла будучи студенткой - в 1958 году в фильме Григория Рошаля «Хмурое утро» (третий фильм трилогии «Хождение по мукам»). Она играла юную революционерку, влюбленную в офицера Рощина (Николай Гриценко). Кустинская считалась одной из самых красивых студенток ВГИКа, и вполне естественно, что за ней пытались приударить многие, в том числе и участники фильма. Однако режиссер строго следил за нравственностью в своем коллективе, не позволяя маститым актерам даже приблизиться к дебютантке. При этом он ни на шаг не отпускал Кустинскую от себя - даже когда она была свободна от работы, он забирал ее с собой на съемочную площадку. Как говорится, от греха подальше. И все же, едва закончились съемки, Кустинская вышла замуж. Правда, ее избранником стал человек, не имевший к фильму «Хмурое утро» никакого отношения. Это был 30-летний режиссер Юрий Чулюкин.

Чулюкин был человеком сложной судьбы. Будучи внебрачным сыном знаменитого мхатовца Михаила Астангова (мама Юрия училась у него в ГИТИСе), он в подростковом возрасте связался с хулиганской компанией и угодил в тюрьму. И хотя до суда дело так и не дошло и его выпустили на свободу, однако здоровье свое он в заключении подорвал - ему отбили почки.

В начале 50-х Чулюкин поступил на режиссерский факультет ВГИКа, а в 1958 году пришел на «Мосфильм». Его первой работой стала комедия «Неподдающиеся», которая вышла на широкий экран через год и тут же сделала ее создателя знаменитым. В том же году Чулюкин женился на Кустинской.

Их знакомство произошло за несколько лет до свадьбы. И оно не оставило в памяти актрисы приятных воспоминаний. Увидев ее в первый раз, Чулюкин засмеялся и сказал своим приятелям:

«Это что за худышка? Разве из нее может получиться актриса?» Кустинская тогда была сильно уязвлена и с тех пор боялась встречаться с Чулюкиным. Но однажды он сам остановил ее в институтском коридоре и предложил роль в своем новом фильме. Кустинская обещала подумать, а Чулюкин взял у нее домашний адрес и уже через день принес сценарий. Так началось их знакомство, которое длилось... всего два дня. На третьи сутки Чулюкин сделал Кустинской предложение и повез показывать ее своей матери. Та выбор сына одобрила, хотя до этого браковала всех девушек, которых сын приводил домой. Чулюкин не стал говорить матери, что собирается в ближайшее время жениться на Кустинской. Видимо, опасался, что мать будет этому препятствовать. Он держал мать в неведении вплоть до дня свадьбы, но, даже когда все-таки решил открыться, сделал это не сам, а с помощью своего приятеля - оператора Германа Шатрова, который позвонил матери Чулюкина и... пригласил ее на свадьбу сына.

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

Всесоюзная известность пришла к Наталье Кустинской в 1963 году, когда она сыграла одну из главных женских ролей в комедии Генриха Оганесяна «Три плюс два». Кустинская играла лейтенанта милиции, которая во время отдыха в Крыму внезапно влюбляется в молодого дипломата. В этой роли снимался Евгений Жариков. На какой-то момент он, видимо, потерял чувство реальности и попытался перенести романтические отношения с Кустинской со съемочной площадки в реальную жизнь.