В 1844 г. Евдокимова назначают командиром Волжского казачьего полка, ему присваивают звание полковника. Он по-прежнему принимает деятельное участие в самых опасных и трагических боевых операциях, подвергаясь постоянным испытаниям и страданиям. За умелые действия в боях 1847—1848 гг. за важный опорный пункт Шамиля аул Гергебиль Евдокимов получил чин генерал-майора и орден св. Владимира 3-й степени.
В 1850 г. он возглавляет командование 2-й бригадой 19-й пехотной дивизии и становится начальником правого фланга Кавказской линии, протянувшейся на 400 верст от Усть-Лабинской вверх по Кубани до подножия Эльбруса.
Колоритные страницы жизни, прославившие Н. И. Евдокимова, открываются в ноябре 1855 г., когда его выдвигают командиром 20-й дивизии и начальником левого фланга Кавказской линии". Новый главнокомандующий князь А. И. Барятинский, хорошо знавший Евдокимова по прежней службе, избирает его своим главным сподвижником в деле покорения Восточного Кавказа в 1857—1859 гг. С декабря 1860 г. до конца боевых действий в регионе на Евдокимова было возложено главное руководство войсками на Западном Кавказе. В полной мере ему пришлось испить до дна горькую чашу Кавказской войны.
Война, развернутая на Западном Кавказе, должна была привести в конечном итоге к присоединению восточного берега Черного моря к России. Для этого надобно было очистить от горцев все прибрежье, но предварительно надлежало сдвинуть с места те массы Закубанского населения (абадзехов, шапсугов, убыхов), которые загораживали доступ к береговым горцам. Исполнителем этого громадного и трудного дела был граф Евдокимов. Таким образом, план войны в последние четыре года состоял в вытеснении горцев и в заселении Западного Кавказа.
Во исполнение этого плана в 1861 г. было решено создать на восточном берегу Черного моря новые станицы и переселить в них до 3,5 тыс. казачьих семейств. Переселение должно было производиться в бывшем линейном казачьем войске целыми станицами, начиная с внутренних полков, Хоперской и Кубанской бригад, и в бывшем Черноморском войске — по округам, для чего ежегодно назначалось известное число семейств, первоначально из Ейского округа, как более удаленного от Кубани100
.Однако исполнение этого решения с первых шагов натолкнулось на совершенно неожиданное затруднение. Казаки отказались исполнить отданное им приказание и соглашались на переселение только тогда, когда им будет объявлено на то высочайшее повеление. Причинами такого неожиданного упорства казаков были: объективная трудность переселения целых станиц, в которых многие казаки уже обжились, построили дома, завели сады и т. п.; поспешность, с которой требовалось начать переселение, и, наконец, отсутствие у войскового начальства высочайшего повеления, которое желали видеть казаки101
. Последняя причина была главнейшая. Последовавший затем высочайший рескрипт, данный 24 июня 1861 г. на имя генерал-адъютанта графа Евдокимова, немедленно рассеял все сомнения.Это дало возможность поселить в течение лета 1861 г. 11 новых станиц и, таким образом, не только упрочить окончательно линии Кубанскую и Лабинскую, но и устроить еще на левом берегу реки Лабы несколько станиц102
.Горцы сразу поняли опасность для них такого образа действий. «Укрепление, — говорили они, — это камень, брошенный в поле: ветер и дождь снесут его; станица — это растение, которое впивается в землю корнями и понемногу обхватывает все поле». Положение о заселении предгорий Западного Кавказа было высочайше утверждено 10 мая 1862 г., но самое заселение началось годом раньше, и все линейные полки, находившиеся в районе Кубанской области, были соединены с черноморскими казаками в одно Кубанское войско103
.В сентябре 1861 г. Александр II прибыл на Кавказ, пожелав лично узнать положение дел. Царь 11 сентября высадился на берег в Тамани и, проведя ночь в Екатеринодаре, направился к войскам, действовавшим против горцев. Он посетил новые укрепления: Дмитриевское, Григорьевское, Усть-Лабинское и Майкопское, участвовал в рекогносцировке на реке Белой и в лагере Верхне-Абадзехского отряда.