Именно с театральных подмостков девочка шагнула и на съемочную площадку. Во время одного из представлений в зале оказалась известная детская писательница Агния Барто, которая тогда работала над сценарием детской комедии «Алеша Птицын вырабатывает характер». 6-летняя исполнительница главной роли настолько ей понравилась, что она посоветовала режиссеру Анатолию Гранику взять ее на одну из ролей в свою картину.
Во время съемок фильма Наташа уже училась в школе, поэтому ей пришлось совмещать творчество с учебой. Так как фильм снимался в Ленинграде почти год, девочке пришлось вместе с Мамой переехать туда жить - им дали номер в гостинице «Астория», Наташу устроили в ближайшую школу.
Следующая большая роль Селезневой в кино случилась через восемь лет - она сыграла в фильме Бориса Барнета «Аленка» (1962). Ее партнерами по съемочной площадке были Василий Шукшин, Николай Крючков, Эраст Гарин.
В 1963 году Селезнева поступила в Театральное училище имени Щукина. На экзаменах вдохновенно читала Пушкина и готовила себя к ролям серьезным, драматическим. А педагоги с первого же курса определили ее по цеху «комедии». И не ошиблись. Настоящий успех к актрисе пришел именно в комедии - в фильме Леонида Гайдая «Операция «Ы» и другие приключения Шурика» она сыграла роль Лиды.
По словам Селезневой, на пробы в эту картину ее пригласил ассистент режиссера. Так как руководство училища строго следило за тем, чтобы студенты не снимались, Селезневой пришлось посетить «Мосфильм» тайно. О том, что будет, если ее утвердят на роль, студентка не боялась, видимо, мало надеясь на успех. Но чудо произошло.
Н. Селезнева вспоминает: «Я появилась на съемочной площадке у Гайдая 18-летней студенткой и, конечно, совершенно не понимала тогда, какая это удача - встреча с таким режиссером. Он умел найти к каждому актеру свой, особый подход. Помните, в новелле «Наваждение» моя героиня и совершенно незнакомый ей Шурик штудируют перед экзаменом один учебник? Они настолько сосредоточены, что все остальное проделывают совершенно механически. «Жарко, разденься!» - советует Лида Шурику и сама, сбросив одежду, остается в купальнике... Так вот, Леонид Иович, окинув меня взглядом, сказал: «Вам в кадре нужно будет раздеться». Я кивнула. «А как у вас с фигурой? Вроде бы не очень...» - «У меня не очень?» - возмутилась я и мгновенно сбросила с себя сарафан. Гайдай довольно улыбнулся: «Вы утверждены!» Потом он говорил, что я сделала это легко и раскованно (а по тем временам это было невероятно), но вместе с тем - «целомудренно», именно так, как ему было нужно...»
Однако, преодолев это препятствие - утверждение на роль, Селезневой предстоял разговор с ректором училища. С дрожью в коленках она отправилась к нему на прием, в глубине души предрекая громы и молнии на свою голову. Однако и здесь студентку ждало чудо: ректор удивительно спокойно отнесся к ее просьбе и отпустил на съемки.
Фильм «Операция «Ы» вышел на экраны страны в 1965 году и стал лидером проката - 1-е место, 69,5 млн. зрителей. Новелла «Наваждение», в которой одну из главных ролей сыграла Селезнева, была удостоена специального приза на кинофестивале в Чехословакии.
Следующей работой Селезневой в кино вновь стала комедия - режиссер с «Беларусьфильма» Виталий Четвериков пригласил ее на главную роль в картину «Саша-Сашенька». На этот раз ей пришлось перевоплотиться в маляра Сашу Крылову, которая мечтает стать актрисой. Партнерами Селезневой на съемочной площадке были известные актеры: Владимир Высоцкий, Лев Прыгунов, Роман Филиппов, Юрий Медведев, Нина Шацкая. Однако публикой фильм был встречен довольно прохладно.
Закончив училище в 1966 году, Селезнева попала в труппу Театра сатиры. Благодаря этому Обстоятельству, в том же году она оказалась в числе тех счастливцев, кому выпала честь участвовать в первых выпусках знаменитого телевизионного «Кабачка «13 стульев», где Селезневой досталась роль жизнерадостной пани Катарины.
Героиня актрисы была первой модницей кабачка, и наряды, в которых она появлялась на экране, затем горячо обсуждались всей женской половиной Советского Союза. Между тем восхищенный зритель был в неведении относительно того, каких нервов стоило актрисе каждое появление в новом наряде на съемочной площадке. К примеру, за появление в мини-юбке (ее привезла из Парижа подруга актрисы) Селезневу наказали денежным штрафом. Кассир так и сказала: «Вы наказаны за слишком короткое платье!»
