В 1936 году заболела её мать (у неё обнаружили рак), и отец нашёл для неё частного врача, который оказался немцем. Больной он помочь так и не сумел, а его присутствие в доме Фёдоровых кое-кем было истолковано превратно. Когда в стране началась кампания против «врагов народа», эта связь сыграла злую шутку с Алексеем Фёдоровым. Он порой нелестно отзывался о некоторых высоких руководителях (на правах человека, работавшего у Ленина, он позволял себе так высказываться), поэтому, когда «ежовщина» охватила всю страну, его постигла участь миллионов несправедливо осуждённых. Летом 1938 года А. Фёдоров был арестован по статье 58 УК и приговорён к десяти годам лишения свободы.
Став дочерью «врага народа», Фёдорова мысленно распрощалась со своей звёздной карьерой. Однако, как это ни странно, арест отца практически не отразился на дальнейшей судьбе актрисы. За первые десять лет своей карьеры в кино она снялась в 22 картинах, причём в большинстве из них в главных ролях. Стоит отметить, что за съёмки в фильмах «Музыкальная история» (1940, 7-е место в прокате — 17,9 млн. зрителей) и «Фронтовые подруги» (1941) Фёдорова была удостоена Сталинской премии.
Однако, как признавалась позднее сама актриса, она мечтала о других ролях — ярких, музыкальных, — а ей приходилось играть героинь, как через кальку списанных друг с друга. Даже пыталась изменить свой имидж, сыграть отрицательную героиню (чтоб курила, пила и ругалась, как базарная торговка), но таких ролей ей никто не предлагал. Так что не всё безоблачно было в тогдашней её кинокарьере.
В конце 30-х годов изменилась личная жизнь актрисы. Брак с Рапопортом окончательно развалился, и в 1939 году актриса встретила свою настоящую любовь. Этим человеком стал лётчик Иван Клещёв. Однако оформить свои отношения официально времени у них не хватило — началась война. Клещёв ушёл на фронт, и в одном из боёв под Сталинградом его самолёт был сбит. Лётчика спасло чудо — он выжил, получив тяжёлые ранения, более месяца пролежал в госпитале, его выписали с диагнозом «не годен к полётам». После этого Героя Советского Союза Ивана Клещёва распределили для дальнейшего прохождения службы в отдел по расследованию авиакатастроф. Фёдорова была несказанно рада такому повороту событий и уже мечтала о свадьбе, но судьбе было угодно расставить всё по-своему. Клещёв вылетел к месту очередной катастрофы под Тамбовом, и самолёт, в котором он находился, был атакован вражеской авиацией. В неравном бою самолёт Клещёва был сбит и разбился. Так Фёдорова вновь осталась одна.
