«С Андреем мы очень подружились. Он был именно хорошим другом, были долгие и теплые отношения, после тяжелого разрыва с Басовым он мою душу очень отогрел. Вот Андрюша, хоть и не имел тогда такого богатства, опыта душевного, — с ним было очень хорошо, он интеллигент настоящий, прекрасный сын своих родителей, я ему за многое благодарна…

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

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

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

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

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

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

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

По слухам, которые курсировали в те годы в артистической среде, брак Фатеевой и Егорова дал трещину за два года до официального развода. Все началось с того, что в 1969 году Фатеева уехала в Румынию на съемки фильма «Песни моря».