Рано дебютировав в кино и сыграв в нем несколько ролей, первой из которых стала Даша в «Розыгрыше» Владимира Меньшова, Евдокия испытала серьезные трудности с поступлением в театральный вуз. Удалось ей это с шестой попытки, когда она уже совсем опустила руки. Мастером, взявшим ее на свой курс в ГИТИСе, оказался Олег Табаков.

В 1985 году, ставя дипломный спектакль, Табаков предложил молодой актрисе роль Жанны д’Арк в спектакле «Жаворонок» по Жану Аную. Как он признался впоследствии, это был единственный случай, когда он взялся ставить пьесу «на актрису».

Спустя год Евдокия удостоилась первой серьезной кинопремии — за лучшую женскую роль на V Всесоюзном фестивале молодых кинематографистов. Эта награда была вручена ей за роль в картине Ольги Наруцкой «Нам не дано предугадать». Среди других кинопремий Евдокии — гран-при «Хрустальный глобус» на МКФ в Карловых Варах за работу в картине «Ниагара» (1991); главный приз за лучшую женскую роль на кинофестивале «Созвездие» (1992) — фильм «Кикс»; специальное упоминание жюри на МКФ в Салониках (1994) — картина «Серп и молот».

На сцене Театра Табакова актриса начала играть со дня его официального открытия в марте 1987-го. В первые годы она сыграла ряд заметных ролей, среди которых Ровена в «Билокси-Блюзе», Степанида Ефимовна в «Затоваренной бочкотаре», Анна Андреевна в «Ревизоре».

Уникальная характерность актрисы раскрылась в работах с такими режиссерами, как Адольф Шапиро («Последние», «На дне»), Андрей Житинкин («Псих»), Миндаугас Карбаускис («Когда я умирала»).

Дважды спектакли, в которых Евдокия играла главные роли, удостаивались премии «Хрустальная Турандот»: «Еще Ван Гог…» Валерия Фокина и «Когда я умирала» Миндаугаса Карбаускиса. Спектакль Карбаускиса также был удостоен «Золотой маски». Международной премией им. Станиславского была отмечена роль Евдокии в спектакле «На дне», где она сыграла Настю.

В 1996 году актрисе были присвоено звание заслуженной артистки России.

В настоящее время Евдокия совмещает игру в театре и съемки в кино с преподаванием актерского мастерства в ряде московских вузов.