В 1845 году он вновь оказался на Кавказе уже в чине полковника. Успешно командуя 3-м батальоном Кабардинского пехотного полка, он обратил на себя внимание наместника Воронцова. Барятинский был ранен еще раз — в ногу, но быстро поправился и в 1847 году был назначен командиром Кабардинского пехотного полка.
В начале 1850 года Барятинский был отозван с Кавказа. Это стало результатом придворных интриг: ему в невесты прочили М. Столыпину, но он не захотел на ней жениться, чем вызвал неудовольствие Николая I.
По ходатайству цесаревича в мае 1850 года Барятинского вернули на Кавказ, произвели в генерал-майоры и назначили состоять при Кавказской линии. В том же году он сопровождал наследника в поездке по Кавказу. Вскоре после этого Барятинский был назначен командиром Кавказской гренадерской бригады, а весной 1851 года — начальником Левого фланга Кавказской линии.
Желая отличиться, Барятинский предпринял ряд экспедиций в Большую Чечню. Прокладывая новые дороги и просеки, разрушая непокорные аулы, он не забывал уделять внимание административному устройству «замиренных» чеченцев и организации нового управления, которое по сути было старым шамилевским управлением.
В 1852 году Барятинский уже стал генерал-лейтенантом. Он внимательно изучал опыт Имамата Шамиля и предлагал свои проекты овладения Кавказом. Его предложения были одобрены Воронцовым и императором. В крепости Грозной даже был куплен дом для размещения новоиспеченной чеченской администрации и запланированы средства на содержание управления «начальника чеченского народа».
В январе 1853 года Барятинский был пожалован чином генерал-адъютанта свиты Его Императорского Величества, а осенью назначен на должность начальника Главного штаба — вторую по значимости в крае. Барятинский собрался было развернуться изо всех сил, но начавшаяся война с Турцией, переросшая в борьбу против коалиции европейских держав, спутала все планы князя по покорению Кавказа.
Покидая Кавказ, Воронцов прочил на свое место Барятинского. Но Николай I решил, что тот еще «не дорос», и назначил временно исполняющим обязанности наместника генерала Реада.
Раздосадованный Барятинский ринулся на фронт и принял участие в сражении 24 июня 1854 года при Кюрюк-Дара, закончившемся поражением 60-тысячной турецкой армии Зарифа-Мустафа-паши от 18-тысячного корпуса под командованием генерал-лейтенанта В. Бебутова. Получив за отвагу очередной орден, Барятинский был назначен состоять при новом императоре.
Стремление нового наместника Муравьева примириться с горцами он считал неоправданной слабостью. А освободившиеся после войны огромные войска предлагал обратить на разгром Шамиля.
Но на пути честолюбивых планов Барятинского стоял Муравьев, для которого мир с Шамилем был делом чести. Он считал, что горцев лучше иметь в кунаках, чем во врагах.
Дело кончилось тем, что 22 июля 1856 года Муравьев был уволен от должности наместника с назначением членом Государственного совета.
26 августа 1856 года Барятинский был произведен в генералы от инфантерии и назначен наместником на Кавказе.
По просьбе нового наместника начальником Главного штаба Отдельного Кавказского корпуса был назначен генерал-майор Д. Милютин — кавказский ветеран, известный военный теоретик и профессор императорской Военной академии. Милютин тоже состоял в свите императора и полностью разделял взгляды Барятинского.
Муравьев, так и не ставший на Кавказе «своим», тяжело переживал опалу. Формальное членство в Госсовете, руководство незначительными комиссиями, почетное шефство над гренадерским полком не могли удовлетворить его кипучую натуру. Муравьев засел за мемуары, опубликованные уже после его смерти под названием «Война за Кавказом в 1855 году». Скончался Николай Николаевич в 1866 году.
Пришествие нового наместника
В октябре Барятинский прибыл к Кавказской армии. Свое вступление в должность он ознаменовал приказом: «Воины Кавказа! Смотря на вас и дивясь вам, я вырос и возмужал. От вас и ради вас я осчастливлен назначением быть вождем вашим и трудиться буду, чтобы оправдать такую милость, счастие и великую для меня честь. Да поможет нам Бог во всех предприятиях на славу государя».
Получив от Александра II полный «карт-бланш» и необходимые средства, Барятинский начал с решительных административных и военных реформ.
Желая освободиться от «бремени распорядительной и исполнительной власти», он передал гражданские дела образованному им же самим Главному управлению наместника кавказского. Администрация Кавказа получила полномочия особого Кавказского министерства.
Театр военных действий он разделил на пять военных отделов; для местного управления учредил округа, подразделенные на приставства, участки или наибства.
Кавказский корпус был переименован в Кавказскую армию, которой он давно уже был по своей численности. В распоряжении наместника оказалось более 200 тысяч солдат, в числе которых были и основные силы, действовавшие в Крымской войне, тогда как все войско имама, включая ополченцев, едва достигало сорока тысяч.