О первом впечатлении, о работе и о дружбе с Евдокимовым рассказывала коллега и подруга Евдокимова, Регина Дубовицкая: «В 1984 году кто-то из артистов сказал, что появился в Москве талантливый мальчик, делает пародии и вроде бы работает в областной филармонии. Я его вызвонила, хотя найти Мишу было непросто. Он в то время снимал даже не комнату, а полкомнаты где-то на окраине. Когда пришел в Останкино, я предложила ему показать пародию. Молчит. Думаю: стесняется человек – редакция, много людей сидит. «Представьте, – говорю, – что это Театр эстрады». – «Я никогда не работал в Театре эстрады». – «Ну, представьте, что это клуб в вашей деревне. Вот вы выходите на сцену. В зале земляки». – «А зачем я им буду что-то показывать, они и так все мои пародии знают». – «Зачем же вы тогда ко мне сюда пришли, если не хотите показывать пародию?». Пауза, а потом он говорит: «Пришел, чтобы познакомиться». Меня зло разобрало – честно. «Ну и как я вам?». Снова пауза. «Все нормально. Еще увидимся», – и ушел. Миша был настоящий, то есть всегда одинаков в поступках, в оценках чего-либо. Без пафоса, без манерности. С таким можно в разведку идти. Верный товарищ. Не подводил никогда. Во-вторых, его было практически не свернуть с пути: если он что-то задумал, то обязательно воплощал это в жизнь. Но при этом он умел слушать и советоваться, хотя трудно было его переубедить. И, в-третьих, не было никаких или–или. Либо он принимал человека, либо нет. Независимо от того, «нужный» ли это влиятельный человек. Мишино «да» всегда было «да».

Параллельно с активной работой в «Аншлаге» Михаил Евдокимов сотрудничал с театрально-концертной фирмой «Музыка». Он не прекращал учиться, и в 1992 году окончил факультет режиссеров эстрады в ГИТИСе. В этом же 1992 году он основал ООО «Театр Евдокимова», который возглавлял до 2004 года. Воспоминаниями о годах учебы делился однокурсник Евдокимова Олег Митяев: «Мы вместе учились в ГИТИСе на режиссёрском факультете. Это было заочное отделение. Поступили в 1986 году. Люди все взрослые, со своими привычками. И мне запомнилось, как каждый из нашей группы во время сессии обедал. Одна актриса из Краснодара приносила на обед из гостиницы бутерброды с чёрной икрой и бутылку шампанского. Другая актриса ела только яблоко, потому что следила за фигурой. Были такие, кто вообще обходился стаканом кипячёной воды. Я брал с собой какие-то банальные бутерброды. А Миша мог купить рядом с метро несколько десятков пирожков с мясом, причём, вместе с лотком, поставить его перед нами и сказать: «Угощайтесь, ребята».
В начале 1990-х годов Евдокимов начал сниматься в кино. На его счету были роли в фильмах «Воспоминание о «Коровьем марше» в 1991 году, «Не хочу жениться» и «Про бизнесмена Фому» в 1993 году, «Не валяй дурака» в 1997 году, «Не послать ли нам гонца?» в 1998 году и «Старые клячи» в 2000 году. Несмотря на то, что все эти роли были похожи друг на друга, как похожи и на самого Евдокимова, все они были очень тепло восприняты аудиторией. А за роль в комедии «Не валяй дурака» артист даже получил приз «За талант, народный юмор и верность традициям отечественного кинематографа» на всероссийском кинофестивале «Созвездие». Галина Евдокимова с теплотой вспоминала московский период жизни с супругом: «Миша был особенным во всем. Многим он казался деревенским простачком, этому способствовал и его сценический образ. Но он был разным. Я чувствовала, что рядом настоящий мужчина. Видела в нем человека, о котором женщина может только мечтать».

Евдокимов никогда не замыкался на одном жанре или формате. Его актерская деятельность переросла в успешную телевизионную карьеру, параллельно с которой шла запись музыкальных альбомов. Ему доверяли создание авторских передач. На экране появлялась передача «С легким паром!» на Первом канале, «Не скуЧАЙ!» и «Михаил Евдокимов в кругу друзей» на телевизионном канале «Россия» и «Надо жить» на ТВЦ. В 1998 году он получил «Золотого Остапа» в номинации «Артист эстрады». Один за другим выходили диски с его монологами и песнями, а в 1999 году он и многие другие известные артисты приняли участие в совместном проекте композитора Евгения Бедненко и Виктора Мережко «Поют звезды театра и кино». Итогом этой работы стал ряд концертов и музыкальный альбом, записанный в США.
Несмотря на феноменальную популярность, Евдокимов никогда не чувствовал себя оторванным от обычных людей. Он часто ездил домой, если выдавалось свободное время, помогал родным деньгами и подарками. Галина Евдокимова рассказывала: «Он не копил. Заработал — потратил. Нужно кому-то — помог. По большим суммам советовался со мной. Он легко расставался с большими деньгами. Когда учился в Новосибирске и жил только на то, что сам зарабатывал, отдал земляку свое теплое зимнее пальто. Сам остался без зимней одежды, мерз! Вот за это я его пилила. Говорю: «О себе-то надо думать! Если бы что еще было в гардеробе, а то единственное пальто». Похожими воспоминаниями делилась и Регина Дубовицкая: «Помню, как первый раз пришла к нему домой. У него в Москве была маленькая двухкомнатная «хрущевка». И меня поразило, что все в ней было завалено какими-то одеялами. «Что это такое у тебя?» – «Ребята с Алтая приехали». – «А что, им больше негде ночевать? Только у тебя?» – «А у меня здесь, считай, Дом колхозника». К нему постоянно приезжали гости с Алтая. Помогал он людям здорово. Кому-то трактор купил, кому-то еще что-то. Но это когда он стал уже по-настоящему зарабатывать. Мишины друзья шли с ним по жизни. Он жил в Москве, но москвичом никогда не был. Главное его местожительство – деревня Верх-Обское. Он пропадал там. Полгода точно проводил. Как-то разыскала его в сентябре по телефону: «Миша, ну ладно ты в деревне. У дочки же занятия в школе начались. Она же все забудет!». И он мне тогда сказал: «Главное, чтоб она деревню не забыла».