При Муравьеве многие офицеры стали покидать Кавказ. А. И. Барятинский также не захотел оставаться с новым командующим. А Муравьев, естественно, не хотел видеть его рядом с собой в должности начальника штаба.
Барятинский был озабочен отправкой с Кавказа своей огромной библиотеки. Муравьев, узнав об этом, сказал ему: «Напрасно вы отправляете вашу библиотеку; ведь вы, по всей вероятности, скоро возвратитесь сюда на мое место»18. Видимо, новый командующий чувствовал шаткость своего положения.
В мае 1855 года просьба А. И. Барятинского об увольнении от службы была удовлетворена. За несколько дней до отставки Барятинский отправляет с оказией письмо М. С. Воронцову, в котором поделился своими мыслями о Муравьеве: «Я полагаю, что генерал Муравьев предан пользам страны и что он приехал сюда с наилучшими намерениями, но, к несчастью, неверно настроенный, очень предубежденный и под впечатлением завистливых убеждений, всегда стремящихся унизить истинную заслугу. Кажется также, что у него не достает такта, что о воспитании его мало заботились и что его развитие не стоит на высоте его положения: у него много деланного и мало естественного. От совокупности всего этого, разумеется, он до сих пор не мог внушить никому никакой симпатии». «Правление здесь, — продолжает Барятинский, — можно смело назвать палочным, во всей его грубости, правление, которое подавляет все честные и хорошие чувства и которого не существует здесь уже давно».
Далее А. И. Барятинский пишет, что он принял должность начальника штаба у Михаила Семеновича только для того, чтобы помочь ему. А впоследствии, когда закончится война и установится мир, он хотел бы покинуть на некоторое время армию и посмотреть, не дадут ли ему место генерал-губернатора. Чтобы освоиться в гражданском управлении, продолжает он, «я был бы несказанно благодарен, если бы вы мне дали по этому поводу ваш совет. Вы мне всегда оказывали столько внимания, что я не боюсь быть нескромным, прибегая к вашей опытности и прося вас не оставить меня вашими советами»19. Но Александр Иванович не стал генерал-губернатором, и ему не потребовались советы Михаила Семеновича по гражданским делам.
Н. Н. Муравьев, вступив в должность, стал знакомиться с подчиненными ему чиновниками. Он спросил В. А. Соллогуба: «Вы автор „Тарантаса“?» — «Да, я», — ответил граф. «Ну, можете сесть в ваш тарантас и уехать», — заявил командующий. И Соллогуб присоединился к покидавшим Кавказ.
Н. Н. Муравьев, желая доказать свое превосходство над М. С. Воронцовым в военном деле, решил взять штурмом осажденную русской армией турецкую крепость Каре. Осада крепости длилась уже около пяти месяцев. Осажденные должны были вот-вот капитулировать, но командующий приказал штурмовать. Штурм провалился, при этом было убито и ранено у штурмовавших 2 генерала, 228 офицеров и более двух тысяч солдат. На второй штурм Муравьев не решился, а вскоре защитники Карса сдали крепость без боя. Несмотря на проведение бессмысленного штурма крепости и понесенные при этом огромные потери, впоследствии он стал именоваться Муравьевым-Карским.
В конечном итоге Н. Н. Муравьев понял, что командование армией и наместничество на Кавказе оказались ему не по плечу, и послал в Петербург просьбу об отставке. 22 июня 1856 года просьба была удовлетворена.
Нельзя не отметить, что у Н. Н. Муравьева хватило мужества признать несправедливость своих нападок на М. С. Воронцова и на Кавказскую армию. А. Л. Зиссерман пишет: «Генерал Муравьев за обедом, который ему давали в Тифлисе в 1856 году, после увольнения его от должностей наместника и главнокомандующего, сознался в своей ошибке, сожалел о письме к Ермолову и отдал полную справедливость достоинствам Кавказской армии»20.
22 июля 1856 года наместником и главнокомандующим Кавказской армии был назначен А. И. Барятинский. А за неделю до этого Барятинский написал Михаилу Семеновичу: «Я буду очень счастлив попасть туда, чтобы возобновить ваши учреждения и мудрые меры, вами заведенные; твердою целью моей службы будет поддерживать дух вашего управления, стремясь уничтожить все следы того, который нас разлучил. Жду также с нетерпением увидеть вас, надеюсь, вы не оставите меня вашими советами и наставлениями, на случай если я все же получу известное вам назначение»21.
М. С. Воронцов с удовлетворением воспринял известие о назначении А. И. Барятинского: «Радуюсь от глубины души во имя той дружбы, которую я к вам питаю, за благо страны, передаваемой в ваше управление. Живо представляем себе радость, которая повсюду распространится, в особенности в Грузии и в Тифлисе. Да поддержит Господь ваше здоровье для прекрасного поста, который вы займете и для которого вы так прекрасно подготовлены!»22.
Храбростью и многими другими чертами Барятинский походил на Воронцова. Михаил Семенович видел в нем преемника, который «довершит то, что ему вероятно исполнить не суждено»23. Так оно и произошло.