Родился в 1804 г., в станице Наурской, в бедной семье фейерверкера Ивана Евдокимова, крестьянина Уфимской губернии, который, будучи взят по набору рекрутом в 1784 г., тянул солдатскую лямку до 1813 г., когда, наконец, его произвели за выслугу лет в прапорщики и назначили начальником артиллерии гарнизона в укреплении Темнолесском. В этом глухом уголке Кавказа провел свое детство в суровой обстановке будущий граф Евдокимов. Родители дали ему крепкое здоровье, природный ум и обучили его грамоте и счетоводству. 16-ти лет Евдокимов поступил вольноопределяющимся в Тенгинский пехотный полк и свыше трёх лет прослужил нижним чином. Случай помог ему выдвинуться. Однажды Евдокимов в чём-то провинился и ожидал строгого наказания; рота, в которой он служил, находилась в составе отряда, прикрывавшего поселения Кавказских Минеральных Вод от ожидавшегося нападения черкесов. Удручённый своей провинностью, Евдокимов решил искупить её отчаянным подвигом. Не говоря никому ни слова, Евдокимов переоделся байгушем (нищим) и самовольно ушёл на разведку в горы, где пробыл свыше двух дней, подвергаясь страшным опасностям. На третий день Евдокимов явился с повинной к своему ротному командиру и доложил ему о местонахождении и силах черкесов. Ему было поручено вести отряд, который и нанес горцам решительное поражение. За этот подвиг Евдокимов в 1824 г. был произведён в прапорщики с переводом в Куринский пехотный полк, расположенный тогда в Дербенте. Начавшаяся в 1826 г. война с Персией ещё более выдвинула Евдокимова, но его первым серьёзным боевым опытом было участие в экспедициях против Кази-Муллы в 1830—1831 гг., во время которых он особенно выделился своей храбростью и распорядельностью при кровопролитном штурме укреплённого урочища Чумкесент, в сражении при Тарках, при обороне крепости Бурной и в бою под Дербентом. В бою под Тарками Евдокимов, командуя взводом куринцев, овладел красным знаменем Кази-Муллы и был ранен пулей, попавшей под левый глаз и прошедшей через голову. Узнав во время лечения, что Кази-Мулла осаждает Дербент, Евдокимов решил во что бы то ни стало присоединиться к полку. На простой рыбачьей лодке пустился он с двумя нижними чинами в открытое море; обманув бдительность горцев, высадился на берег и, случайно избегнув плена, пробрался сквозь цепь горских постов и явился в полк. Отчаянный подвиг Евдокимова обратил на него общее внимание. Ему было объявлено Высочайшее благоволение, и он был награждён орденом св. Анны 3-й степени. За его рану горцы впоследствии прозвали Евдокимова Уч-Гезом, то есть трехглазым, в переносном смысле — «прозревающим мысли и сердца». В 1834 г. Евдокимов был произведён в поручики и переведён в Апшеронский пехотный полк, с которым участвовал во множестве дел и, между прочим, в штурмах укреплённых аулов Гимры и Гоцатль, а в деле при Ашальтинском мосту был контужен. За отличия Евдокимов в 1837 г. был произведён в штабс-капитаны и пожалован орденом св. Владимира 4-й степени с бантом. Вместе с тем он был назначен адъютантом к генералу Клюки-фон-Клюгенау, который, оценив способности Евдокимова, впоследствии подружился с ним и переводил его с собой на новые места служения: в 1838 г. — в Ахалцыхскую провинцию и в 1839 г. — в Дагестан. Евдокимов всюду выказал себя незаменимым сотрудником, благодаря отличному знанию и опытности по строевой и военно-хозяйственной части, а также и близкому знакомству с горцами. В 1840 г. Евдокимов, произведённый за отличие в капитаны, принимал участие в летней экспедиции генерала Галафеева в Чечню и находился в кровопролитном бою на р. Валерик. В том же году Евдокимов участвовал и в решительных действиях генерала Клюки-фон-Клюгенау против Шамиля, завершившихся разгромом сил его под Гимрами. В начале 1841 г. майор Евдокимов был назначен Койсубулинским приставом, на обязанности которого лежало управление горскими обществами. В 1842 г. Шамиль пытался возмутить округу, но Евдокимов с ничтожными силами овладел мятежными аулами Харачи и Унцукуль. Генерал-лейтенант Фези не находил слов благодарить Евдокимова, «совершившего этот блистательный подвиг с решительностью, отважностью и пламенным усердием, которыми он всегда отличался». В Унцукуле, однако, Евдокимов едва не погиб. Прибыв туда всего лишь с ротой Апшеронского полка, он приказал собраться старикам и старшинам. Во время переговоров к Евдокимову сзади подкрался фанатик-горец и кинжалом нанес ему рану в спину; кинжал прошёл насквозь, чудом не задев сердца. Евдокимов, не растерявшись, выхватил шашку, быстро обернулся и одним ударом разрубил горца наискось, от плеча до середины груди. Происшествие это произвело на горцев потрясающее впечатление. Старшины подхватили падавшего замертво Евдокимова и бережно отнесли его в ближайшую саклю. Тут-то и сказалось искреннее отношение горцев к своему приставу. Видя, что ротный фельдшер не знает, как приступить к подаче помощи, горцы приняли заботы о раненом на себя. Они разыскали местного искусного хакима (врача), издалека привезли его и поручили выходить Евдокимова, который очнулся лишь на третий день после ранения. Благодаря заботливому уходу и своей богатырской натуре, Евдокимов через два месяца уже отправился в новую экспедицию. За оказанные подвиги Евдокимов был произведён в подполковники и награждён орденом св. Георгия 4-й степени. В мае 1842 г. он участвовал в известной по печальному исходу экспедиции генерала Граббе в Ичкерию; получив в конце года в командование отряд на Нижне-Сулакской линии, принял с ним в 1843 г. участие в Аварской экспедиции генерала Клюки-фон-Клюгенау и, возвратившись на Сулак, зорко охранял единственный путь сообщения с Россией при невероятно трудных условиях. Присоединенный в конце 1843 г. со своим отрядом к войскам генерала Фрейтага, Евдокимов участвовал в отражении полчищ Шамиля от укрепления Низового, в освобождении укреплений Миатлинского и Темир-Хан-Шуры. Смелые экспедиции обратили на Евдокимова внимание императора Николая I, и он был произведён в полковники и награждён орденом св. Станислава 2-й степени. В 1844 г. Евдокимов неоднократно участвовал в Дагестанских экспедициях генерала Лидерса, действуя иногда вполне самостоятельно, как, например, при рекогносцировке на с. Кодор, где он обнаружил 3-тысячное скопище горцев и искусно от них отбился. В конце июня 1844 г. Евдокимов был назначен командиром Волгского казачьего полка Терского войска. Помимо прямых обязанностей по командованию полком, Евдокимов исполнял ряд административных поручений по охране края, по усовершенствованию охраны Кисловодской кордонной линии, по устройству наблюдательной линии по р. Сулак и другие работы. С назначением Евдокимова в начале 1846 г. командиром Дагестанского пехотного полка, который он сам же формировал, вновь наступил для него период выдающейся боевой деятельности. В 1846 г. он участвует с полком в экспедициях генерала Бебутова, завершившихся разгромами Шамиля при ауле Кутиши. В 1847—1848 гг. Евдокимов в составе отряда князя Воронцова принял участие в овладении Гергебилем и Салтами и был награждён орденом св. Владимира 3-й степени, а в 1850 г. произведён в генерал-майоры и назначен сперва командиром 1-й бригады 20-й пехотной дивизии, а потом 2-й бригады 19-й пехотной дивизии, и ему же было вверено начальствование над правым флангом Кавказской линии на протяжении до 600 верст. Главной задачей Евдокимова было поставлено бдительное охранение линии и обеспечение наших поселений, но в действительности это было, по его выражению, «бремя защиты слабой страны со слабыми силами». Евдокимову предстояло оборонять огромную дистанцию 12-ю казачьими полками, из которых 4 были рассыпаны на внутренних постах и по почтовому тракту, да 8 батальонами пехоты, большая часть которой была разбросана гарнизонами по укреплениям и станицам. С неимоверным трудом и с опасностью допустить прорыв Евдокимов имел возможность в лучшем случае сосредоточить 10—12 рот пехоты и до 2 тысяч конницы. Противник же его, Мухамед-Эмин, «второй Шамиль», имел возможность бросить на любой пункт линии 6—7 тысяч. Ряд экспедиций, предпринятых Евдокимовым в 1850 г., выяснил, что необходимо наши передовые укрепления перенести с р. Лаба на р. Белая и начать систематическое стеснение закубанских горцев. Упорным трудом в течение 5 лет Евдокимов положил прочное основание к покорению Западного Кавказа. Сознавая недостаточность своего образования, Евдокимов в генеральском чине с увлечением занялся изучением военных наук. Здоровый и положительный ум и огромный опыт давали ему полную возможность разбираться критически в сложных вопросах и, как свидетельствуют современники, вести интересные научные беседы. Евдокимов в 1854 г. составил записку «О предположениях, полезных для исполнения на правом фланге Кавказской линии», в которой изложил основания прочного покорения враждебного края. До 1855 г. деятельность Евдокимова ограничивалась лишь экспедициями. 28 декабря 1855 г. состоялось назначение Евдокимова командиром 20-й пехотной дивизии и начальником левого фланга Кавказской линии. Прибыв в начале 1856 г. на главный театр военных действий, он в два с половиной года покорил Большую, Малую и Нагорную Чечню, взял Ведено, загнал Шамиля в Гуниб и закончил войну на Восточном Кавказе, принудив Шамиля сдаться. Чин генерал-лейтенанта, звание генерал-адъютанта (и графский титул — вот ряд боевых наград, которыми были удостоены подвиги Евдокимова. Среди главнейших его наград и был орден св. Георгия 3-й степени № 503, полученный 17 апреля 1859 г.:
В то время как на Восточном Кавказе всё было покончено, на Западном результаты предвещали лишь отдалённую развязку. Князь Барятинский, считая неотложным предпринять решительные действия, передал это дело в руки Евдокимова, назначив его в 1860 г. начальником всех находившихся там войск. Прибыв в край, Евдокимов объявил войскам, что экспедиции будут продолжаться непрерывно. Не допуская и в мыслях слабости, Евдокимов высказал: «Первая филантропия — своим; горцам же я считаю вправе предоставить лишь то, что останется на их долю после удовлетворения последнего из русских интересов». Эта политическая программа станет вполне понятной, если принять во внимание, что Евдокимову предстояло покорить край, на который Западная Европа имела в то время свои виды: ей был нужен свободный Кавказ для различных авантюр против России. Вот почему Евдокимов совершенно правильно признал, что надо не только покорить край, но и водворить здесь русских. С чрезвычайной энергией Евдокимов принялся за дело. Испытанная на Восточном Кавказе система движения вглубь страны, прокладывая дороги, вырубая просеки и т. д., вплоть до выселения горцев на плоскость или в Турцию, а также одновременное водворение русских, надёжно обеспечивали успех. Наступление в 1860 г. встретило сильное сопротивление со стороны шапсугов, а другие племена или встречали наши войска относительно дружелюбно (натухайцы), или пытались вступать в переговоры (абадзехи). К концу 1860 г. Евдокимов покончил с шапсугами, оттеснив их за главный хребет к берегу моря. Весной 1861 г. Лабинская линия была уже перенесена на р. Фарс, причем различные мелкие народы (темиргои, бесленеи, тамовцы и др.) или были уничтожены, или бежали в Турцию. Встревоженные успехами воинственные абадзехи попытались в сентябре вступить в переговоры, но потерпели неудачу, так как Евдокимов категорически высказал депутатам, что требует не мирного соседства, а безусловной покорности и переселения в назначенные места, причем дал месячный срок на принятие решения. Абадзехи взялись за оружие. Евдокимов, непрерывно устраивая кордонную линию по р. Фарс, в феврале 1862 г. перешёл в наступление и к концу марта успел очистить пространство между pp. Белая и Лаба, а в мае перенёс передовую линию на р. Белая. Теперь предстояло перенести военные действия в горы, чтобы оттеснить непокорных горцев и прижать их к берегу моря. Организовав наступление несколькими отрядами и оставив часть войск для прикрытия переселенцев, Евдокимов лично принял активное участие в операциях. Руководя действиями отрядов (Адагумского, Даховского, Пшехинокого и Шапсугского), он неуклонно приводил в исполнение свой план и к весне 1863 г. овладел значительной территорией, на которой и было водворено до 4 тысяч казачьих семейств в 24 новых станицах. В течение лета передовая линия была продвинута на pp. Пшех и Курджипс, а затем покончено и с абадзехами. К концу 1863 г. вся Кубанская область была покорена, и для окончательного овладения Западным Кавказом оставалось смирить племена убыхов, джигетов и шапсугов, стесненных в узком пространстве между крутыми склонами главного Кавказского хребта и Чёрным морем, Абхазией и течением Пшады. Успешные действия войск в феврале — марте 1864 г. вызвали панику среди ещё не покорённых горцев. 21 мая 1864 г. все 5 колонн соединились при урочище Кбааде, откуда главнокомандующий великий князь Михаил Николаевич отправил императору Александру II историческую телеграмму:
.
Последними боевыми наградами Евдокимова, покорившего и Западный Кавказ, были чин генерала от инфантерии и орден св. Георгия 2-й степени № 100
Почётной наградой Евдокимову было также назначение 1 ноября 1864 г. шефом Дагестанского пехотного полка. 7 января 1865 г. Евдокимов был назначен состоять при главнокомандующем Кавказской армией и уволен от всех должностей. Последние годы жизни он мирно провел в Пятигорске, где умер 23 мая 1873 г. и похоронен в ограде местного собора; детей у него не было.
Быстрое выдвижение Евдокимова создало ему немало врагов и завистников и послужило причиной, что в печати о нём появились разноречивые суждения: одни скептически относились к его достоинствам, другие, наоборот, признавали в нём замечательного военного деятеля и человека, а третьи распускали неблагоприятные для Евдокимова слухи, обвиняя его в злоупотреблениях. Но нельзя не указать на отзыв об Евдокимове князя А. И. Барятинского, который однажды хулителям Евдокимова высказал следующее: «Вы говорите, что он свободно относится к казённому интересу. Пусть будет так… Но какой ущерб он мог нанести казне? Ну, пусть будет полмиллиона, миллион, даже 2 миллиона. Ну, что значат даже 2 миллиона для такого государства, как Россия? А он мне Кавказ завоюет, и Россия сохранит этим сотни миллионов рублей и десятки тысяч жизней русских людей».
После Евдокимова остался архив, состоящий из официальных документов и из частных бумаг и записок. Архив этот в 1888 г. поступил в распоряжение редакции журнала «Русская старина», в котором частью и печатался в различные годы (1888. Т. LVII. № 4 и 10; 1889. № 3, 5, 6, 7, 8 и 11; 1890. № 2).