Родился в 1804 году в станице Наурской (Чеченская Республика), в бедной семье фейерверкера Ивана Евдокимова и донской казачки Дарьи Савельевны.
Отец Николая Евдокимова в высокие чины не вышел, но в жизни преуспел. В глухом уголке Кавказа и провел свое детство будущий граф Евдокимов. Несмотря на суровую обстановку в юные годы, родители Николая Ивановича дали ему крепкое здоровье, природный ум, обучили его грамоте и счетоводству.
В 16 лет Евдокимов поступил в Тенгинский пехотный полк и больше трех лет прослужил там нижним чином. Но один случай помог ему получить звание прапорщика. Однажды Николай Евдокимов совершил проступок на службе и очень боялся наказания. В то время близ Кавказских Минеральных Вод ожидалось нападение черкесов. Николай Иванович находился в составе отряда, прикрывавшего местное поселение. И тут он решил искупить свою вину храбрым и отчаянным подвигом. Никому не сказав о своем замысле, он переоделся нищим и в одиночку ушел на разведку в горы, где пробыл несколько дней, подвергаясь большим опасностям.
После разведки Евдокимов вернулся с повинной к своему командиру и доложил о выясненном им лично местонахождении черкесов. Командир поручил ему вести отряд, который и нанес горцам поражение. Так Николай Евдокимов был переведен в Куринский пехотный полк, расположенный тогда в Дербенте.
В 1826 году началась война с Персией и тогда в экспедициях против Кази-Муллы Николай Евдокимов снова отличился храбростью и распорядительностью. Командуя взводом куринцев, он овладел красным знаменем Кази-Муллы и был ранен пулей, прошедшей через голову. За это ранение горцы прозвали его Уч-Гезом, трехглазым, «прозревающим мысли и сердца». Не смотря на ранение, Евдокимов вернулся на поле боя. На простой рыбачьей лодке вышел он в открытое море, обманув тем самым бдительность горцев. Потом высадился на берег и, случайно избегнув плена, пробрался сквозь горское оцепление и вернулся в родной полк. После этого отчаянного подвига к Николаю Ивановичу было обращено еще больше внимания — было объявлено Высочайшее благоволение, он был награжден орденом Святой Анны 3-й степени.
В 1834 году Николай Евдокимов был произведен в поручики и переведен в Апшеронский пехотный полк. В деле при Ашильтинском мосту был контужен. В 1837 году за отличия был произведен в штабс-капитаны и пожалован орденом Святого Владимира 4-й степени с бантом.
Множество славных и смелых боев пережил Николай Евдокимов — бой на реке Валерик, бои против Шамиля, экспедиции в Ичкерию и Дагестан, в Унцукуле, где едва не погиб. Генерал-лейтенант Фези говорил о Евдокимове так: