Родилась 3 мая 1956 года в Москве.

Заслуженная артистка РСФСР (28.09.1984).

В 1977 году окончила Всесоюзный государственный институт кинематографии (мастерская Сергея Бондарчука и Ирины Скобцевой).
Уже на втором курсе сыграла в своем первом фильме "От зари до зари". К окончанию ВГИКа на её счету было уже пять ролей. Наиболее интересные работы тех лет — большая роль Танюши в "Степановой памятке" (реж. К.В. Ершов) и крошечный эпизод ("девка на возу") в "Степи" (реж. С.Ф. Бондарчук). Известность в профессиональных кинематографических кругах Наталья Андрейченко приобрела после роли красавицы-сибирячки Насти Соломиной в "Сибириаде" Андрея Кончаловского. Ещё одной замечательной работой тех лет является трагическая роль Ольги в "Торговке и поэте" Самсона Самсонова.
В 1983 году на экраны вышли два самых популярных фильма с её участием: "Военно-полевой роман" Петра Тодоровского и "Мэри Поппинс, до свидания" Леонида Квинихидзе. Роль Любы Антиповой в фильме Петра Тодоровского "Военно-полевой роман" остаётся вершиной актёрской карьеры Андрейченко.
За 1985-1988 годы актриса сыграла главные роли у Александра Белинского в музыкальном фильме "Марица" и в мелодраме Эрнеста Ясана "Прости" (вместе с Игорем Костолевским и Виктором Мережко). Восьмидесятые годы были самыми удачными в творчестве актрисы. Не случайно в течение трех лет она признавалась лучшей актрисой года.
В 1992 году снялась в сериале Сергея Бондарчука "Тихий Дон" в роли Дарьи, в 1994 году — в нескольких голливудских фильмах: "Ночная стража", фильм Шелла "Свечи в темноте", а также "Маленькой Одессе", получившей "Серебряного льва" на фестивале в Венеции в 1994 году.

Она играла в театре Анатолия Васильева. Известна ролью Нади в спектакле "Серсо" в постановке Васильева, премьера которого состоялась в 1985 году. Затем она выходила на драматическую сцену с Максимилианом Шеллом. Это было в Театре-студии Табакова в спектакле "Вера, Любовь, Надежда" по пьесе австрийского драматурга Едена фон Хорварда. Следующей ее работой был спектакль "Прекрасное лекарство от тоски", поставленный Иосифом Райхельгаузом в театре "Школа современной пьесы".

В 1996 году совместно с группой Natasha & GooSee («Наташа и гуси») записала альбом MOST, где выступила в роли вокалистки.
Была соведущей Павла Веденяпина в телепрограмме "Поехали" (ОРТ), для телеканала "ТВ-Центр" в 1999 году сняла авторскую программу "Русские в мировом кино". В 2010 году стала одним из членов жюри украинского шоу талантов «Украина слезам не верит». В 2011 году совместно с Дмитрием Нагиевым вела реалити-шоу «Мама в законе» на телеканале «Перец».

Первый муж — российский композитор Максим Дунаевский.
Второй муж — австрийский актёр и кинорежиссёр Максимилиан Шелл (1930-2014), в браке с ним в 1986—2005 годах.

В 1991 году эмигрировала в США к мужу, Максимилиану Шеллу. После развода в 2005 году вернулась в Россию.
В одном из своих последних интервью актриса сказала, что живет там, где работа. Сейчас живет в Мексике и США.

Премия Ленинского комсомола (1984).
Приз на Международном фестивале в Вальядолиде (Испания, 1984) — за лучшее исполнение женской роли в фильме "Военно-полевой роман".
Лучшая актриса года по результатам опроса журнала «Советский экран» (1987).