Родилась 19 июня 1945 г. в Москве. Ее отец - Игорь Николаевич Полинковский - работал фотографом. Мать - Елена Семеновна Селезнева - была художницей. В детстве Наталья Селезнева носила фамилию отца, позже взяла фамилию матери.
Впервые вышла на сцену в шестилетнем возрасте. Исполнила роль девочки Глории в спектакле "Тридцать сребреников" по пьесе Говарда Фаста, поставленном в Центральном театре Советской Армии (ныне Центральный академический театр Российской армии). Еще школьницей начала сниматься в кино. В фильме Анатолия Граника "Алеша Птицын вырабатывает характер" (1953) исполнила роль девочки Саши, в картине Иосифа Гиндина и Исаака Менакера "Девочка и крокодил" (1956) сыграла Катю Пастушкову.
В 1966 г. Наталья Селезнева окончила Театральное училище им. Б. В. Щукина (ныне Театральный институт им. Бориса Щукина при Государственном академическом театре им. Евгения Вахтангова). Выпускница курса профессора Анатолия Борисова.
С 1966 г. по н. в. является актрисой Московского академического театра сатиры. Исполняла роли в постановках: "Интервенция" по пьесе Льва Славина, "Горе от ума" по комедии Александра Грибоедова, "Клоп" по произведению Владимира Маяковского, "Гнездо глухаря" по пьесе Виктора Розова, "Последние" по произведению Максима Горького, "Неаполь - город миллионеров" по трагикомедии Эдуардо де Филиппо.
В 1966 г. Наталья Селезнева была приглашена к участию в съемках юмористической телепередачи "Кабачок "13 стульев". Этот проект, в котором были задействованы многие актеры Театра сатиры, шел на Центральном телевидении до 1980 г. Действие телеспектакля происходило в польском кафе (кабачке). Наталья Селезнева играла роль одного из его завсегдатаев - пани Катарину.
Широкую известность в кино Наталья Селезнева получила, исполнив роль студентки Лиды в комедии Леонида Гайдая "Операция "Ы" и другие приключения Шурика" (новелла "Наваждение", 1965). В дальнейшем она сыграла еще в двух картинах Гайдая - "Иван Васильевич меняет профессию" по мотивам пьесы Михаила Булгакова "Иван Васильевич" (1973) и "Не может быть!" по произведениям Михаила Зощенко (1975). Также снималась в фильмах: "Приключения желтого чемоданчика" по повести Софьи Прокофьевой (1970, режиссер Илья Фрэз), "По улицам комод водили" (1978, Марк Генин и Николай Ковальский), "Берегите мужчин!" (1982, Александр Серый), "Примадонна Мэри" (1998, Анатолий Эйрамджан), "Вы не оставите меня..." по повести Сергея Ашкенази "Григорий Евсеевич" (2006, Алла Сурикова). Последняя роль к настоящему времени - Агнесса Леопольдовна в мелодраме "Новогоднее дежурство" (2014, Флюза Фархшатова и Уланбек Баялиев). В общей сложности Наталья Селезнева снялась в более чем 50 кинокартинах, сериалах и фильмах-спектаклях.
Народная артистка РФ (1996).
Награждена орденами Дружбы (2006) и Почета (2015).
Замужем. Супруг - народный артист СССР, президент Московского драматического театра им. М. Н. Ермоловой Владимир Андреев (род. 1930). Сын - Егор (род. 1969, дипломат).