Михаил Евдокимов родился 6 декабря 1957 года в городе Сталинске (ныне Новокузнецк) Кемеровской области. Отец, Сергей Васильевич, — рабочий. Мать, Анна Петровна, родилась в 1924 году, работала на шахте. У Евдокимова шесть братьев и сестер. В 1958 году семья переехала в село Верх-Обское Смоленского района Алтайского края. По окончании школы Михаил Евдокимов учился в Барнауле в культпросветучилище на отделении балалаечников, затем работал шлифовщиком на Алтайском моторном заводе, администратором в столовой. Служил в армии в Нижнем Тагиле. В 1978—1979 годах занимал должность художественного руководителя сельского дома культуры в селе Усть-Катунь Смоленского района Алтайского края. В 1979 году поступил в Новосибирский институт торговли, был капитаном команды КВН. В 1981 году бросил учебу и уехал в Москву, за что был отчислен из института. Впоследствии, в 2000-х годах, все же окончил институт торговли, к тому времени переименованный в Сибирский университет потребительской кооперации (специальность — «экономика и управление на предприятии»).
Артист эстрады и кино
В 1981 году неудачно поступал в Московское эстрадно-цирковое училище.
В 1983 году приглашен в Московскую областную филармонию в качестве артиста разговорного жанра, а затем — в Москонцерт.
8 марта 1984 года дебютировал на телевидении в праздничной программе «Огонек».
С 1989 года работал в концертно-театральной фирме «Музыка». Известность к артисту пришла в 1989 году после участия в телевизионной программе «Аншлаг».
В 1992 окончил факультет режиссеров эстрады ГИТИСа в Москве.
С 1992 по апрель 2004 года являлся директором ООО «Театр Евдокимова». Снялся в нескольких фильмах. Выпустил несколько компакт-дисков с песнями в своём исполнении.
Губернатор Алтайского края
Планы политической карьеры у Михаила Евдокимова возникли еще в 1995 году. Тогда он баллотировался в Государственную думу от Барнаула, а в 2003 году хотел идти на выборы в Подмосковье от Аграрной партии. В январе 2004 года Евдокимов сообщил о намерении претендовать на пост алтайского губернатора на предстоящих в марте выборах.
Евдокимов одержал победу на выборах главы Алтайского края 4 апреля 2004 года, обойдя во втором туре баллотировавшегося на третий срок действующего губернатора Александра Сурикова. На выборы Евдокимов шёл под лозунгом «Шутки в сторону!». Но вся избирательная кампания велась под жестким административным давлением команды действующего губернатора Сурикова. СМИ окрестили победу Евдокимова «синдромом Шварценеггера» (актёр, победивший на выборах в губернаторы Калифорнии). Вскоре губернаторские выборы в России были упразднены.
Гибель
7 августа 2005 года в 9:20 по московскому времени Евдокимов погиб в результате автомобильной аварии на трассе Бийск-Барнаул, в 100 километрах от Барнаула и 20 км от Бийска. Евдокимов и его жена Галина в сопровождении водителя и охранника направлялись в село Полковниково Косихинского района, где проходили мероприятия по случаю 70-летия со дня рождения космонавта Германа Титова.
По факту аварии было возбуждено уголовное дело. В период сразу после аварии официальные лица отрицали какую-либо возможность того, что катастрофа была подстроена. Тем не менее его гибель могла иметь хотя бы косвенное отношение к политической борьбе в крае: незадолго до трагедии у Евдокимова, конфликтовавшего с краевыми органами внутренних дел, были отняты машины сопровождения. Ряд журналистов и политиков высказали предположения, что Евдокимова могли убить за то, что он пытался бороться с коррупцией, связанной, вероятно, с контрабандой (в том числе наркотиков) с территории соседнего Казахстана, с которым граничит Алтайский край. Официальное следствие не проводило проверок ни одной из версий, выходящей за предположение об «обычном ДТП». Аркадий Вольский вспоминал, что незадолго до гибели Евдокимов произнёс ему фразу: «Батька, меня наверное шлёпнут»…
Авария произошла в тот момент, когда губернаторский «Мерседес» пытался обогнать автомобиль «Тойота-Марино», за рулём которого находился житель Алтайского края Олег Щербинский. В результате «Мерседес», уходя влево, на высокой скорости (около 200 км/ч) коснулся «Тойоты», вылетел в кювет и врезался в землю глубокого кювета, затем задел дерево. Водитель «Тойоты», а также пассажиры этой машины — женщина и двое детей — не пострадали. Супруга Евдокимова, Галина Николаевна, находившаяся вместе с ним в «Мерседесе», в результате аварии получила тяжелые травмы. Водитель губернатора Иван Иванович Зуев и охранник Александр Юрьевич Устинов погибли вместе с Михаилом Евдокимовым на месте от травм, несовместимых с жизнью.
Семья
Вдова — Галина Николаевна, домохозяйка. Дочь Анна окончила Московский гуманитарный университет по специальности «международный туризм», в настоящее время занимается организацией концертов.