Николай в это время искал кандидата на должность кавказского наместника, поскольку престарелый князь М.С. Воронцов уже давно просился в отставку. Однако любой из известных генералов или аристократов, которые обычно ставились на должность «проконсула» Кавказа, согласились бы на этот пост лишь при условии увеличения численности кавказской армии. Все понимали, что для решающих успехов на Кавказском театре военных действий у Отдельного кавказского корпуса сил было явно недостаточно. Незнатный Муравьев, хотя дважды робко попросил у царя подкреплений, однако согласился ехать на Кавказ, получив категорический отказ в них. Для Муравьева новое назначение было чрезвычайно лестно.
В конце 1854 г. Муравьев получил чин генерал-адъютанта и был назначен наместником Кавказа и командиром отдельного Кавказского корпуса. На этой должности он пребывал до 1856 г., когда вышел в отставку. До конца жизни он оставался членом Государственного совета.
Став наместником Кавказа, Н.Н. Муравьев был настроен на решительные действия. Он прекрасно понимал, что главной целью русских войск в Закавказье в 1855 г. должен стать Карс – завладев которым, можно уже думать и о дальнейших успехах, вплоть до похода на Стамбул!
Карс возводился с помощью лучших английских инженеров. Всю зиму 1854–1855 гг. турки при помощи англичан спешно продолжали совершенствовать оборонительную систему крепости. Крепость считалась неприступной – в том числе и потому, что Соганлугские горы, разделяющие Карс и Эрзерум, здесь образовывали весьма круто смотрящую в небо гору Карадаг, на вершине которой был возведен сильный редут, который и соединили весьма защищенным лагерем с крепостью. Каменный вал окружал предместье, сам же город защищали высокие стены с воротами и башнями. Со стороны Эрзерума близ города протекала река Карс. На хребте горы – цитадель, ощетинившаяся орудиями и спускающаяся к кромке города отнюдь не одним ярусом стен.
С тех пор как Муравьев был под стенами крепости в последний раз, она значительно усилилась. Англичане постоянно инспектировали артиллерию и стрелковые войска турок. Среди командиров в Карсе было много поляков и венгров, а венгры Кмети и Кольман являлись генералами турецкой армии.
Опираясь на Карс и Эрзерум, турецкое командование, подталкиваемое союзниками, намеревалась в кампанию 1855 г. переломить ход боевых действий на Кавказе и попытаться вытеснить русских из Грузии. Несмотря на победы Кавказского корпуса в 1854 г., положение русских войск вызывало тревогу. Особенно сложной являлась проблема снабжения их всем необходимым. После появления союзного флота в Черном море русский флот уже не мог выполнять функции этого снабжения. Мелкие русские крепости по восточному черноморскому побережью были в большинстве своем эвакуированы из-за ударов союзников с моря. Военно-Грузинская дорога была еще очень несовершенна и, кроме того, находилась под постоянными ударами горцев. Путь через Дагестан и Баку также подвергался нападениям горцев и являлся тяжелым и длинным.
Тем не менее, прибыв в Тифлис в марте 1855 г., Н.Н. Муравьев в начале июня начал поход на Карс. В его распоряжении было около 21,5 тыс. пехотинцев, 3 тыс. кавалеристов и небольшие отряды грузинских и армянских ополченцев. Противник имел решительное превосходство в живой силе. О штурме думать пока не приходилось – не было даже надлежащей артиллерии. Муравьев предпринял осаду. Он блокировал крепость со всех сторон так прочно, что вскоре ее защитники уже весьма ощутимо почувствовали тяжелую руку русского наместника. Карс был полностью обложен к концу июля.
Окружность, подлежащая блокаде, составляла 50 верст. Условия горной местности делали невозможной абсолютную блокаду, и иногда в крепость прорывались отряды с продовольствием. Однако сколько-нибудь существенного общения осажденных с внешним миром русские не допускали. Все отряды, выходившие из Карса для добычи продовольствия, успешно громились. В крепости начался голод, который усугубила неожиданно ранняя и холодная для этой местности осень: 28 августа в горах выпал снег. Зная о бедственном положении гарнизона, турецкое командование отправило ему на помощь большой отряд из Эрзерума, однако он был разгромлен 31 августа высланным Муравьевым войском.
Голод в Карсе усиливался, что вело к падению дисциплины в гарнизоне. Однако командование крепости во главе с Вассиф-пашой и английским полковником У-Ф. Вильямсом принимало решительные меры против попыток дезертирства: расстрелы следовали за расстрелами. Надежда не покидала защитников Карса: турецкий главнокомандующий генералиссимус Омер-паша во главе 30 тысяч десанта, прибывшего в Батум, собирался идти на выручку своим подчиненным. 12-тысячный корпус Вели-паши, недавно разбитый русскими, был усилен в Эрзеруме новобранцами и грозил появиться в тылу у гяуров. И наконец до осажденных 11 сентября 1855 г. дошло радостное известие: пал Севастополь.