Yevdokimova graduated from St. Petersburg State University of Nautical Engineering (formerly, Leningrad Shipbuilding Institute); her post-graduate studies were in the field of applied and computational mathematics. She worked at Leningrad Shipbuilding Institute, then, after 1982, at TELEKOM Advanced Training Institute, where she rose from senior lecturer to associate professor and provost. Between 1994 and 2007, she was a member of the Legislative Assembly of St. Petersburg (first, second, and third convocation) and headed the Commission for Social Issues. She is Executive Secretary of the St. Petersburg Council for Human Rights and an adviser to the Chairman of the Federation Council of the Federal Assembly of the Russian Federation. Since 2009, Yevdokimova has headed legislation research and analysis for ERC Bellona.