Наталья Фатеева родилась 23 декабря 1934 года в Харькове. В 1956 году на Киностудии им. Довженко состоялся ее дебют в кино. Актриса сыграла роль Тани Олениной в фильме "Есть такой парень" режиссера Виктора Ивченко. В середине 1950-х годов Фатеева познакомилась с режиссером Владимиром Басовым, ставшим впоследствии ее мужем. В 1957 году она сыграла одну из главных ролей в его фильме "Случай на шахте восемь". Также снималась в картинах "Капитан "Старой черепахи" Всеволода Воронина и Генриха Габая и "Дело "пестрых" Николая Досталя.
В 1960-х годах Фатеева снялась в картинах "Битва в пути" Владимира Басова и "Наш общий друг" Ивана Пырьева. Популярность актрисе принесла роль дрессировщицы Зои в комедии Генриха Оганесяна "Три плюс два" (1963, по пьесе Сергея Михалкова "Дикари"), где ее партнерами были Андрей Миронов, Евгений Жариков, Геннадий Нилов и Наталья Кустинская.