Николаю Ивановичу Евдокимову было суждено стать одной из ключевых фигур кавказской истории XIX века. Первый раз он был ранен в левую часть лица, что впоследствии привело к появлению прозвища Учгез, то есть Трёхглазый. Во время второго ранения пуля раздробила ему правую сторону лица, обе ноги были прострелены, а грудь ушиблена камнями. В третий раз фанатик вонзил ему кинжал в левый бок, а потом в правое плечо. Но Евдокимов, русский офицер, всегда возвращался в строй.
В 1821 году он начинает службу в качестве подпрапорщика Тенгинского пехотного полка. Ермоловское время было насыщено боевыми походами, схватками с горскими партиями, которые непрестанно тревожили линию. Рота, в которой в должности писаря выпало служить Евдокимову, прикрывала нарождающиеся курорты на Кавказских Минеральных Водах. Здесь и произошел случай, возможно, определивший судьбу будущего покорителя Кавказа. По собственной инициативе отправившись в разведку, Евдокимов сумел собрать важные сведения об ожидающемся набеге немирных горцев. Это позволило успешно отразить нападение, и наградой стало не только забвение былого прегрешения, но и произведение в прапорщики. В 1824 году Евдокимов отправляется в Дербент, где, получив первый офицерский чин, продолжает службу уже в Куринском пехотном полку.
С каждым годом военный опыт молодого офицера возрастал. Боевая биография Евдокимова пополнилась участием в боевых столкновениях с неприятелем на территории Кубинского и Ширванского ханств, во время войны с Персией.
Весной 1831 года горский предводитель Кази-мулла захватил селение Тарки и осадил русский гарнизон в крепости Бурной. Ситуация складывалась отчаянная. Малочисленный русский гарнизон во главе с майором Федосеевым в течение восьми дней отражал натиск превосходящих сил неприятеля, но без поддержки извне был обречен на гибель. Им на помощь выступил отряд генерала С.В. Каханова, в состав которого входил Куринский полк. В результате ожесточенного сражения неприятель был отброшен.
Во время боя прапорщик Евдокимов получил приказ возглавить резерв и поджечь ту часть Тарков, в которой закрепились мюриды. Он, «несмотря на сильное сопротивление неприятеля и на полученную им рану, исполнил в точности возложенное на него поручение», что было отмечено командованием. Он предпринял нападение на большую саклю, где, по его представлению, мог укрыться сам горский предводитель, и с потерями был отброшен неприятелем. Причём сам Евдокимов оказался ранен в левую часть лица, что впоследствии привело к появлению прозвища Учгез, то есть Трёхглазый. Но не только шрам стал причиной такого имени. Проницательность будущего генерала, умение разгадывать замыслы неприятеля наделяли его в глазах современников особыми выдающимися качествами.
Суровый опыт не пропал даром, и «в дальнейшем он никогда не позволял себе необдуманных и авантюрных атак, неподготовленных операций и действий без тщательной разведки. Изучение противника стало для него обычным, рутинным занятием, однако его познание превратилось со временем в отличительную черту генерала. В отличие от многих коллег, он отказался от стандартного ведения боя или войсковой операции, вначале он старался проанализировать все особенности предполагаемого противника, а уж потом, найдя его слабые стороны и подобрав подходящее время, решался на наступательные действия, стараясь замаскировать его от горцев», — отмечают историки.
Раненый офицер оказался на излечении в крепости Бурной, где познакомился со своей будущей женой, дочерью местного коменданта Александрой Александровной Федосеевой. В это же время Евдокимова наградили орденом Святой Анны III степени. Кроме того, он был повышен в чине и стал подпоручиком.
Стремясь побыстрее вернуться в строй и вместе со своими товарищами разделить тяготы борьбы с Кази-муллой, он на лодке отправился в осажденный Дербент и сумел пробраться в город. Когда «после бурного плавания, на вторые сутки лодка стала подходить к Дербенту, два гребца, заметив большие огни, стали уверять, что это пожар; но Евдокимов догадался, что это неприятельские бивуаки, и сначала поспорил об этом с гребцами, но после, вспомнив, что те из боязни попасть к неприятелю, пожалуй, и вздумают вернуться, перестал спорить, подтвердил их догадку насчёт пожара и, таким образом, доплыл до города».
Грозный имам так и не сумел добиться поставленной цели. Он был отброшен от Дербента, а русские войска начали постепенно теснить мюридов, возвращая под свой контроль потерянные территории. В составе отряда генерал-адъютанта Н.П. Панкратьева Евдокимов участвует в усмирении Табасарани и Каракайтага, штурмует селения Дювек и Эрпели. В начале декабря 1831 года он принимает участие в сражении с мюридами в урочище Чумескент, стоившем русским войскам больших жертв. Достаточно сказать, что в ходе боя погиб командир отряда полковник Миклашевский, были убиты и ранены до 350 солдат и офицеров.
В 1832 году судьба свела Евдокимова с генералом Францем Карловичем Клюки фон Клюгенау (Клугенау).
Под его началом Евдокимов сражается с Кази-муллой в урочище Эльсустау, не позволяя осуществиться планам главы мюридов закрепиться в шамхальских владениях.
Если 1833 год прошёл относительно спокойно, то следующий оказался наполнен походами и сражениями. Новым местом службы Евдокимова становится Апшеронский пехотный полк. По мере разрастания вооруженного противостояния на Северо-Восточном Кавказе у Евдокимова не раз появлялась возможность показать свои качества в боях с отчаянными мюридами. И он каждый раз демонстрировал свои навыки расчетливого и храброго командира. Заслуги произведенного в поручики Евдокимова были отмечены в ходе штурма аула Гимры и селения Гоцатль.
С 1834 года новым местом службы Николая Ивановича становится Апшеронский пехотный полк.
Видимо, он сумел произвести должное впечатление на новом месте службы, так как на следующий год его избирают полковым казначеем. На него обратил внимание император, высказавший свое высочайшее благоволение подданному, о действиях которого столь лестно сообщалось в поступавших реляциях. Очередной наградой офицеру стал орден Святого Владимира IV степени с бантом.
