Yevdokimov was born in Stalinsk (now Novokuznetsk), western Siberia. After a long career as a comedian, actor and singer, he had entered politics by 2003. In April 2004, he became governor of the Altai Krai region of Russia after defeating incumbent Aleksandr Surikov in the elections. Surikov was the candidate supported by Russian President Vladimir Putin and Yevdokimov became one of the few Russian governors not to have Putin's support. Later, in part because of this election, Putin supported a law which was successfully passed that governors would no longer be directly elected.
In March 2005, Yevdokimov was impeached by the local legislature in a no confidence vote which passed by a vote of 46 to 5. He remained in office, but was under increasing pressure to resign. On August 7, 2005, Yevdokimov was killed in a car accident while traveling on the Russian route M52 20 km from the city of Biysk. His car grazed another car then ran off the road and hit a tree. Yevdokimov's driver and bodyguard died along with him, while his wife, who was also in the car, survived. The driver of the car that collided with Yevdokimov's car, Oleg Scherbinsky, was convicted of breaking traffic laws with fatal result and sentenced to spend 4 years in a settlement colony. Scherbinsky's conviction was followed by car drivers' protests and demonstrations all over Russia - the Russian government officials, even of the lowliest rank, have a habit of not following the traffic rules, casually driving over the speed limit, in the wrong lane or using the blinking lights on top of their car, creating a lot of problems on the road and endangering regular drivers. The traffic police usually is lenient in enforcing the rules against them, and regular drivers are often blamed in case of a collision with a government car. On March 23, 2006, Scherbinsky's conviction was overturned on appeal and he was released.
Yevdokimov was married (Galina) and had one daughter (Anna). He also had another daughter, Anastasia, with a woman named Nadezhda Zharkova. After Yevdokimov's death, Zharkova twice sued Galina and Anna for inheritance, but never arrived to the courthouse, and both cases were dismissed due to Zharkova's absence in court.
- Remembering the "Cow march" (1991) — talker, singer
- About businessman Foma (1993) — Foma
- I do not want to get married! (1993) — police officer
- Full house and Co (1996)
- Don't Play the Fool... (1997) — Filimon
- Why Don't We Send... a Messenger? (1998) — Ivan
- Old Hags (2000) — Timofey Y. Astrakhantsev, businessman from Astrakhan
- Voronov, Konstantin (2006-02-04). Шофер отпущения. Kommersant (in Russian) № 20 (3351). Retrieved 2009-02-27.
- Автомобилисты объединились в волне протестов против приговора водителю (in Russian). NEWSru. 2006-02-13. Retrieved 2009-02-27.
- Олег Щербинский оправдан (in Russian). Lenta.Ru. 2006-03-23. Retrieved 2009-02-27.
- "Иск о споре за наследство Михаила Евдокимова оставлен без рассмотрения". RIA Novosti. Retrieved 2011-01-21.