Родился в 1804 году в станице Наурской (Чеченская Республика), в бедной семье фейерверкера Ивана Евдокимова и донской казачки Дарьи Савельевны.

Отец Николая Евдокимова в высокие чины не вышел, но в жизни преуспел. В глухом уголке Кавказа и провел свое детство будущий граф Евдокимов. Несмотря на суровую обстановку в юные годы, родители Николая Ивановича дали ему крепкое здоровье, природный ум, обучили его грамоте и счетоводству.

В 16 лет Евдокимов поступил в Тенгинский пехотный полк и больше трех лет прослужил там нижним чином. Но один случай помог ему получить звание прапорщика. Однажды Николай Евдокимов совершил проступок на службе и очень боялся наказания. В то время близ Кавказских Минеральных Вод ожидалось нападение черкесов. Николай Иванович находился в составе отряда, прикрывавшего местное поселение. И тут он решил искупить свою вину храбрым и отчаянным подвигом. Никому не сказав о своем замысле, он переоделся нищим и в одиночку ушел на разведку в горы, где пробыл несколько дней, подвергаясь большим опасностям.

После разведки Евдокимов вернулся с повинной к своему командиру и доложил о выясненном им лично местонахождении черкесов. Командир поручил ему вести отряд, который и нанес горцам поражение. Так Николай Евдокимов был переведен в Куринский пехотный полк, расположенный тогда в Дербенте.

В 1826 году началась война с Персией и тогда в экспедициях против Кази-Муллы Николай Евдокимов снова отличился храбростью и распорядительностью. Командуя взводом куринцев, он овладел красным знаменем Кази-Муллы и был ранен пулей, прошедшей через голову. За это ранение горцы прозвали его Уч-Гезом, трехглазым, «прозревающим мысли и сердца». Не смотря на ранение, Евдокимов вернулся на поле боя. На простой рыбачьей лодке вышел он в открытое море, обманув тем самым бдительность горцев. Потом высадился на берег и, случайно избегнув плена, пробрался сквозь горское оцепление и вернулся в родной полк. После этого отчаянного подвига к Николаю Ивановичу было обращено еще больше внимания — было объявлено Высочайшее благоволение, он был награжден орденом Святой Анны 3-й степени.

В 1834 году Николай Евдокимов был произведен в поручики и переведен в Апшеронский пехотный полк. В деле при Ашильтинском мосту был контужен. В 1837 году за отличия был произведен в штабс-капитаны и пожалован орденом Святого Владимира 4-й степени с бантом.

Множество славных и смелых боев пережил Николай Евдокимов — бой на реке Валерик, бои против Шамиля, экспедиции в Ичкерию и Дагестан, в Унцукуле, где едва не погиб. Генерал-лейтенант Фези говорил о Евдокимове так:

«…совершивший этот блистательный подвиг с решительностью, отважностью и пламенным усердием, которыми он всегда отличался».

Богатырская натура Евдокимова помогала ему после тяжелых и смертельных ранений довольно быстро восстанавливаться и снова отправляться в новые экспедиции. За свои многочисленные подвиги Николай

Иванович был произведен в подполковники и награжден орденом Святого Георгия 4-й степени.

Упорным трудом в течение 5 лет Евдокимов положил прочное основание к покорению Западного Кавказа. В 1860 году князь Барятинский назначил будущего атамана командующим войск в Кубанской области, а в 1862 году он стал начальником области. По вступлении на службу, Евдокимов объявил, что экспедиции буду проходить непрерывно: «Первая филантропия — своим; горцам же я считаю вправе предоставить лишь то, что останется на их долю после удовлетворения последнего из русских интересов».

Николай Иванович разработал стратегию с двумя основными пунктами: выселение горцев на плоскость или в Турцию, и одновременное водворение русских. С поставленной задачей атаман справился, чем показал достойный пример потомкам.

К концу 1863 года вся Кубанская область была покорена. Для окончательного овладения Западным Кавказом оставалось усмирить племена убыхов, джегетов, шапсугов.

В год завершения Кавказской войны Евдокимов решил завершить и свою службу. В 60 лет он ушел в отставку, 43 года из которых были отданы армии. Послевоенные годы Николай Иванович провел в Пятигорске, в окружении родных и близких.