Фильм "Три плюс два" вышел на экраны страны в 1963 году и занял в прокате 4-е место, собрав на своих сеансах 35 млн. зрителей.

В 1964 году Фатеева снялась сразу в двух удачных картинах: у режиссера Фрунзе Довлатяна в "Здравствуй, это я!" и у Евгения Карелова в "Детях Дон-Кихота". Стоит отметить, что роль Люси в первом фильме Фатеева до сих пор считает одной из лучших в своей кинокарьере.

В 1965 году Фатеева впервые съездила в США (первый ее заграничный вояж состоялся тремя годами раньше). Во время этой поездки наша героиня побывала в Голливуде. Вот что она вспоминает об этом: "Мы попали на площадку, где снимался фильм "Кто боится Вирджинии Вулф". Ричард Бартон и Элизабет Тейлор снимали эту картину и никого не пускали. Но к нам вышли. И мы с ними разговаривали. Я помню, что Тейлор очень маленького роста. Я сама невысокого роста, метр шестьдесят пять, но рядом со мной стояла женщина на высоких каблуках, которая была мне под подбородок...

В личной жизни наша героиня не испытывала недостатка от внимания мужчин. По ее же словам: "Бывало, на фестивале танцуешь с замминистра, и он шепчет в ухо: "Я тебе все-все сделаю, все куплю, ни в чем нуждаться не будешь... А я притворяюсь глухой...

И все-таки в конце 60-х Фатеева в очередной раз вышла замуж, причем за человека достаточно известного. Ее избранником стал летчик-космонавт 30-летний Борис Егоров. В октябре 1964 года он совершил полет в космос на корабле "Восход" и получил за это звание Героя Советского Союза. Их встреча состоялась совершенно случайно. Подруга нашей героини встречалась с другом Б. Егорова. Однажды она решила провести у себя дома вечер и попросила своего знакомого привести с собой какого-нибудь друга. Взамен обещала пригласить на вечер подругу со своей стороны. Этой парой и оказались Фатеева и Егоров. Так состоялось их знакомство, которое вскоре завершилось свадьбой. В 1969 году Наталья Фатеева родила дочку, которую назвали Наташей.

Второй брак нашей героини оказался таким же непрочным, как и первый. Прожив вместе пять лет, они развелись.

Наталья Фатеева вспоминает: "Когда мы с ним познакомились, он мне показался надежным, спокойным. Пока "завоевывал" меня, вел себя очень достойно, я бы даже сказала, красиво. Но стали мы с ним жить - "и тут... Разные мы люди оказались, разные стремления у нас были, даже книги по-разному мы с ним читали. Его любимая тема для разговоров была - машины и их лошадиные силы, часами мог об этом говорить... Когда мы разводились, от его благородства не осталось и следа. Он утащил у меня машину, отсудил квартиру - я потом жила в коммуналке. Все это я бы могла ему простить. Но то, что он свою дочь, которой сейчас 24 года, в последний раз видел в двухлетнем возрасте, этого я понять не могу. В голове не укладывается: что же за мужья у меня были, что же за отцы из них получились...

По слухам, которые курсировали в те годы в артистической среде, брак Фатеевой и Егорова дал трещину за два года до официального развода. Все началось с того, что в 1969 году Фатеева уехала в Румынию на съемки фильма "Песни моря". В нем она снималась в главной роли вместе с популярным румынским певцом Даном Спатару. Плененный красотой советской актрисы, певец, который всегда считался донжуаном, решил за нею приударить. По словам самой Натальи Фатеевой: "Спатару - блистательный актер, совершенно уникальный человек, там как раз все самое интересное осталось за кадром... Однако приличное расстояние, отделяющее Бухарест от Москвы, видимо, не помешало недоброжелателям актрисы сообщить об ее "романе" законному супругу.