Став дочерью «врага народа», Фёдорова мысленно распрощалась со своей звёздной карьерой. Однако, как это ни странно, арест отца практически не отразился на дальнейшей судьбе актрисы. За первые десять лет своей карьеры в кино она снялась в 22 картинах, причём в большинстве из них в главных ролях. Стоит отметить, что за съёмки в фильмах «Музыкальная история» (1940, 7-е место в прокате — 17,9 млн. зрителей) и «Фронтовые подруги» (1941) Фёдорова была удостоена Сталинской премии.

Однако, как признавалась позднее сама актриса, она мечтала о других ролях — ярких, музыкальных, — а ей приходилось играть героинь, как через кальку списанных друг с друга. Даже пыталась изменить свой имидж, сыграть отрицательную героиню (чтоб курила, пила и ругалась, как базарная торговка), но таких ролей ей никто не предлагал. Так что не всё безоблачно было в тогдашней её кинокарьере.

В конце 30-х годов изменилась личная жизнь актрисы. Брак с Рапопортом окончательно развалился, и в 1939 году актриса встретила свою настоящую любовь. Этим человеком стал лётчик Иван Клещёв. Однако оформить свои отношения официально времени у них не хватило — началась война. Клещёв ушёл на фронт, и в одном из боёв под Сталинградом его самолёт был сбит. Лётчика спасло чудо — он выжил, получив тяжёлые ранения, более месяца пролежал в госпитале, его выписали с диагнозом «не годен к полётам». После этого Героя Советского Союза Ивана Клещёва распределили для дальнейшего прохождения службы в отдел по расследованию авиакатастроф. Фёдорова была несказанно рада такому повороту событий и уже мечтала о свадьбе, но судьбе было угодно расставить всё по-своему. Клещёв вылетел к месту очередной катастрофы под Тамбовом, и самолёт, в котором он находился, был атакован вражеской авиацией. В неравном бою самолёт Клещёва был сбит и разбился. Так Фёдорова вновь осталась одна.

Надо отдать должное актрисе, несмотря на драматизм всего происходящего в стране и в её личной судьбе, она не прекращала попыток вызволить из тюрьмы отца. Для этого ей даже пришлось напроситься на приём к Лаврентию Берии. Он тайно симпатизировал знаменитой актрисе и готов был многое для неё сделать в обмен на её благосклонность. По воспоминаниям, через такую «помощь» Берии тогда прошли многие известные женщины страны. Вполне вероятно, что не избежала этой участи и Фёдорова. В результате в конце лета 1941 года её отца выпустили на свободу. Однако годы отсидки не прошли для 56-летнего Фёдорова даром. Из-за обморожения в лагере ему ампутировали пальцы на обеих руках. Жизнь на свободе продолжалась для него недолго, и 22 сентября 1941 года Алексей Фёдоров скончался. А вскоре Фёдорову и двух её сестёр постигло новое горе — на фронте погиб их младший брат Иван.

Берия не оставил своих ухаживаний за знаменитой актрисой. В декабре 1943 года он пригласил её к себе в особняк на улице Качалова, объяснив своё приглашение просто: «Моя супруга любит вас и хочет отметить ваш день рождения в узком кругу». Отказать всесильному наркому Фёдорова не смогла, хотя в душе глубоко презирала его. В гостях терпения актрисы хватило только на первый час общения с Берией. Когда выяснилось, что никакой жены наркома на вечеринке не будет, что эту встречу организовал лично он, Фёдорова внезапно вспылила и оскорбила Берию. Тот тут же приказал ей убираться из его дома. Когда она вышла на улицу, Берия догнал её на крыльце и вручил букет роз. При этом он мрачно произнёс:

— Это букет на вашу могилу!

После этой встречи и грозного предупреждения Берии актриса ждала только одного — ареста. Однако его тогда так и не последовало. Постепенно жизнь вошла в своё русло, и Фёдорова успокоилась. Она не могла даже догадываться, что её ждёт.

Осенью 1942 года Фёдорова, будучи на выставке американского кино в Москве, познакомилась с корреспондентом американской газеты «Юнайтед пресс» Генри Шапиро.