В кампании 1829 г. бригада Муравьева отличилась во время похода и взятия крепости Ахалцых, возведенной на левом берегу реки Поцхо, на высокой скале. Муравьев участвовал в переговорах с командованием гарнизона этой крепости, после которых крепость сдалась. За Ахалцых Муравьев стал кавалером ордена Св. Георгия уже 3-й степени.

Прошло много лет. В судьбе и карьере Муравьева были взлеты и падения: он, обидевшись на Николая I, уходил в отставку, затем — когда становился необходим — его вновь призывали послужить державе. Так в 1832–1833 гг. он совершил поездку в Египет и Турцию. Значительную роль Муравьев сыграл в заключении Ункяр-Искелесийского договора между Россией и Османской империей.

Накануне Крымской войны Н.Н. Муравьев служил в Варшаве в должности командира гренадерского корпуса. В конце 1854 г. он получил назначение командующим русскими войсками в Финляндии. В конце ноября генерал-от-инфантерии Н.Н. Муравьев по пути к новому месту службы находился в Петербурге. Там он был вызван императором в Зимний дворец.

Николай в это время искал кандидата на должность кавказского наместника, поскольку престарелый князь М.С. Воронцов уже давно просился в отставку. Однако любой из известных генералов или аристократов, которые обычно ставились на должность «проконсула» Кавказа, согласились бы на этот пост лишь при условии увеличения численности кавказской армии. Все понимали, что для решающих успехов на Кавказском театре военных действий. Отдельного кавказского корпуса сил было явно недостаточно. Незнатный Муравьев, хотя дважды робко попросил у царя подкреплений, однако согласился ехать на Кавказ, получив категорический отказ в них. Для Муравьева новое назначение было чрезвычайно лестно.

В конце 1854 г. Муравьев получил чин генерал-адъютанта и был назначен наместником Кавказа и командиром отдельного Кавказского корпуса. На этой должности он пребывал до 1856 г., когда вышел в отставку. До конца жизни он оставался членом Государственного совета.

Став наместником Кавказа, Н.Н. Муравьев был настроен на решительные действия. Он прекрасно понимал, что главной целью русских войск в Закавказье в 1855 г. должен стать Каре — завладев которым, можно уже думать и о дальнейших успехах, вплоть до похода на Стамбул!

Каре возводился с помощью лучших английских инженеров. Всю зиму 1854–1855 гг. турки при помощи англичан спешно продолжали совершенствовать оборонительную систему крепости. Крепость считалась неприступной — в том числе и потому, что Соганлугские горы, разделяющие Каре и Эрзерум, здесь образовывали весьма круто смотрящую в небо гору Карадаг, на вершине которой был возведен сильный редут, который и соединили весьма защищенным лагерем с крепостью. Каменный вал окружал предместье, сам же город защищали высокие стены с воротами и башнями. Со стороны Эрзерума близ города протекала река Каре. На хребте горы — цитадель, ощетинившаяся орудиями и спускающаяся к кромке города отнюдь не одним ярусом стен.

С тех пор как Муравьев был под стенами крепости в последний раз, она значительно усилилась. Англичане постоянно инспектировали артиллерию и стрелковые войска турок. Среди командиров в Карее было много поляков и венгров, а венгры Кмети и Кольман являлись генералами турецкой армии.

Опираясь на Каре и Эрзерум, турецкое командование, подталкиваемое союзниками, намеревалась в кампанию 1855 г. переломить ход боевых действий на Кавказе и попытаться вытеснить русских из Грузии. Несмотря на победы Кавказского корпуса в 1854 г., положение русских войск вызывало тревогу. Особенно сложной являлась проблема снабжения их всем необходимым. После появления союзного флота в Черном море русский флот уже не мог выполнять функции этого снабжения. Мелкие русские крепости по восточному черноморскому побережью были в большинстве своем эвакуированы из-за ударов союзников с моря. Военно-Грузинская дорога была еще очень несовершенна и, кроме того, находилась под постоянными ударами горцев. Путь через Дагестан и Баку также подвергался нападениям горцев и являлся тяжелым и длинным.

Тем не менее, прибыв в Тифлис в марте 1855 г., Н.Н. Муравьев в начале июня начал поход на Каре. В его распоряжении было около 21,5 тыс. пехотинцев, 3 тыс. кавалеристов и небольшие отряды грузинских и армянских ополченцев. Противник имел решительное превосходство в живой силе. О штурме думать пока не приходилось — не было даже надлежащей артиллерии. Муравьев предпринял осаду. Он блокировал крепость со всех сторон так прочно, что вскоре ее защитники уже весьма ощутимо почувствовали тяжелую руку русского наместника Каре был полностью обложен к концу июля.

Окружность, подлежащая блокаде, составляла 50 верст. Условия горной местности делали невозможной абсолютную блокаду, и иногда в крепость прорывались отряды с продовольствием. Однако сколько-нибудь существенного общения осажденных с внешним миром русские не допускали. Все отряды, выходившие из Карса для добычи продовольствия, успешно громились. В крепости начался голод, который усугубила неожиданно ранняя и холодная для этой местности осень: 28 августа в горах выпал снег. Зная о бедственном положении гарнизона, турецкое командование отправило ему на помощь большой отряд из Эрзерума, однако он был разгромлен 31 августа высланным Муравьевым войском.

Голод в Карее усиливался, что вело к падению дисциплины в гарнизоне. Однако командование крепости во главе с Вассиф-пашой и английским полковником У.-Ф. Вильямсом принимало решительные меры против попыток дезертирства: расстрелы следовали за расстрелами. Надежда не покидала защитников Карса: турецкий главнокомандующий генералиссимус Омер-паша во главе 30 тысяч десанта, прибывшего в Батум, собирался идти на выручку своим подчиненным. 12-тысячный корпус Вели-паши, недавно разбитый русскими, был усилен в Эрзеруме новобранцами и грозил появиться в тылу у гяуров. И наконец до осажденных 11 сентября 1855 г. дошло радостное известие: пал Севастополь.

Об этом узнал и Муравьев — и 17 сентября четыре колонны русских войск пошли на приступ. Были взяты передовые укрепления, но для штурма главного укрепления Карса — Вели-Табии не хватило свежих резервов. Муравьев приказал отступать.

Неудача приступа не сказалась на боевом духе осаждавших. Современник так описывал посещение Муравьевым полевого госпиталя, где находились раненые при штурме:

«Ни стона, ни вопля не было ниоткуда слышно; на приветствия же главнокомандующего в каждой палате страдальцы отзывались бодро и с жаром выражали надежды свои на скорое выздоровление, дабы снова идти на приступ Карса и отомстить туркам за павших товарищей и случившуюся неудачу. При посещении полков в их лагерях выбегали из палаток, среди здоровых, с подвязанными руками легко раненные офицеры и нижние чины, которые не хотели отставать от своих частей и поступать в госпитали. “Турку, — говорили солдаты, — нельзя с одного раза разбить”».

Вновь началась осада. Муравьев решил больше не повторять штурма, а усилить блокаду, стягивая кольцо вокруг крепости все туже и туже. По инициативе молодого графа М.Т. Лорис-Меликова, в будущем — известнейшего военного и государственного деятеля России, был создан отряд из грузин, армян, азербайджанцев, курдов, который громил обозы с продовольствием, пытавшиеся пробраться в Каре Помощь осажденным не подходила, запасы продовольствия кончились, и нормой становилось массовое дезертирство турок Гарнизон терял до 150 человек в сутки — помимо убегавших.