17 апреля 1848 года Муравьёв был принят вновь на службу с назначением состоять по запасным войскам и 18 апреля прикомандирован к генералу от инфантерии В. И. Тимофееву главным начальником запасных батальонов 3-го, 4-го и 5-го пехотных корпусов. С 13 сентября назначен членом Военного совета и, наконец, с 20 декабря командовал Гренадерским корпусом, с которым выступил к границам Венгрии; 31 мая 1850 года был удостоен ордена св. Александра Невского. Муравьёв постепенно вновь приобретал доверие государя, и 6 декабря 1853 года был произведён в генералы от инфантерии и 29 ноября 1854 года пожалован генерал-адъютантом с назначением наместником Кавказским и командиром Отдельного Кавказского корпуса. Ему предстояло руководить войсками на Кавказском театре Крымской войны.

С назначением Муравьёва «неумолкаемому хабару» (кавказское местное выражение, означающее слово «новость»), догадкам и хитросплетениям не было границ. Одни считали его нелюдимым, каким-то пугалом, чуть не людоедом; другие – человеком с закаленным сердцем, лишенным всяких добрых чувств, а иные – просто устарелым, грубым, не обладающим современными взглядами, необходимыми для высшей административной деятельности, хотя не чуждым высшего образования.

В январе 1855 года Муравьёв прибыл на Кавказскую линию, откуда из крепости Грозной написал А. П. Ермолову письмо, признанное им самим впоследствии нетактичностью; в нём он нелестно отозвался о порядках в армии:

«В углу двора обширного и пышного дворца, в коем сегодня ночую, стоит уединенная, скромная землянка ваша, как укоризна нынешнему времени. Из землянки вашей при малых средствах исходила сила, положившая основание крепости Грозной, покорению Чечни. Ныне средства утроились, а все мало да мало. Деятельность вашего времени заменилась бездействием; тратящаяся ныне огромная казна не могла заменить бескорыстного усердия, внушенного вами подчиненным вашим для достижения предназначаемой вами цели. Казна сия обратила грозные крепости ваши в города, куда роскошь и довольства жизни привлекли людей посторонних. Все переменилось, обстроилось; с настойчивостью и убеждением в правоте своей требуют войск для защиты; войска обратились в горожан, и простота землянки вашей не поражает ослабевших воинов Кавказа, от коих дух хотя и не исчез, но силы стали немощны. Таковое состояние дел, конечно, подало повод и к частным злоупотреблениям начальников. Хотя солдата не грабят, но пользуются трудами его как работою тяглового крестьянина, состояние, которое солдат предпочитает строевой службе. Посудите, какое мое положение. Исправить в короткое время беспорядки, вкоренившиеся многими годами беспечного управления, а в последнее время и совершенным отсутствием всякой власти и управления, – труд великий, поздних последствий которого я не увижу и который доставит мне только нарекание всего населения. Но вы, зная меня, убедитесь, что это меня не останавливает: если не достигну конца, то дам направление сему великому делу, поглощающему силы и кару России. В землянку вашу послал бы их учиться; но академия эта свыше их понятий. Не скажу, чтобы здесь не было покорности; напротив того, здесь все покорны; но покорность эта не приводит их к изучению своих обязанностей, а только к исполнению того, что прикажут. Надобно пока и этим довольствоваться с надеждою на время, которое выкажет сотрудников, ибо дарований здесь встречается более чем в России, но все погрязло в лени и усыплении. От многих слышал я справедливые суждения, что ваша Грозная крепость служила основанием покорения Чечни…»

Это письмо огорчило Ермолова, а все военное сословие на Кавказе глубоко оскорбилось и начало выражать громкий протест. Вскоре на это письмо появился ответ молодого офицера, князя Д. И. Святополк-Мирского, быстро распространившийся среди публики:

«Неужели мы, кавказские служивые, должны безропотно покоряться этому приговору и со стыдом преклонять пред ним голову. Нет, наша совесть слишком чиста для такого унижения. Не стали немощными и бессильными те войска, которые победили многочисленных врагов под Баш-Кадыкларом, Курюк-Дара и на Чолоке. Мы не обманывали Россию в течение четверти века; она смело может гордиться нами и сказать, что нет армии на свете, которая переносила бы столько трудов и лишений, сколько Кавказская. Нет армии, в которой бы чувство самоотвержения было бы более развито. Здесь каждый фронтовой офицер, каждый солдат убежден, что не сегодня, то завтра, не завтра, так послезавтра он будет убит или изувечен. А много ли в России кавказских ветеранов? Их там нет почти, кости их разбросаны по всему Кавказу. Письмо, написанное новым главнокомандующим в крепости Грозной и распространенное по Кавказу и России, изумило нас и огорчило; но недолго будет наше уныние. Наше чувство чуждо подлого унижения; мы покорны, но покорны царской воле и закону, но не бранному слову. Мы поднимаем брошенную нам перчатку пред судом России и потомства. Пусть нами руководят мудрые начертания; пусть гениальная рука укажет путь – мы готовы на все, что возможно человеку, на всякие жертвы и лишения. Сколько бы ни было жертв и страданий частных, во всяком случае, это исполинское соревнование поведет ко благу и славе нашего отечества. Нам остается вознести ко Всевышнему усердные молитвы, дабы потомство сказало, что вождь был достоин армии, а армия достойна вождя».

Оба этих письма были впоследствии опубликованы И. А. Пузыревским в «Русской старине» (1872 г., т. IV, с. 542–546).

Муравьёв отнесся снисходительно к поступку молодого офицера, и князь Мирский был переведен «по собственному желанию» в Крым.

Муравьёв приехал в Тифлис 1 марта. Приезд его произвел общее смущение, однако не столько видом и толками, сколько известием о кончине императора Николая I, печальным вестником коего явился сам Муравьёв, узнавший о том от фельдъегеря незадолго до въезда в Тифлис. На первом приеме Муравьёв произвел на представлявшихся приятное впечатление своими остроумными разговорами и замечаниями, но вскоре не сошёлся со своим начальником штаба князем А. И. Барятинским, покинувшим Кавказ под предлогом болезни. Вступив в командование корпусом, Муравьёв отдал приказ, в котором самым лестным образом отзывался о войсках, на подвиги коих «более полвека с гордостью и изумлением Россия внимает», и призывал их стать полными «рвения и готовности за святое дело» в наступившую для России годину испытаний.

В начале июня 1855 года русская армия двинулась к Карсу. В составе отряда для действий против крепости было всего 21200 пехоты, 3000 регулярной кавалерии и столько же казаков, 400 грузинской и армянской милиции, артиллерийский парк состоял из 88 орудий (в основной массе лёгких). Гарнизон Карса состоял, по разным оценкам от 19000 до 33000 человек под командованием Вассифа-паши, там же была группа британских военных советников во главе с полковником Уильямсом; близ Баязета находилось около 12000 человек под начальством Вели-паши, в Эрзеруме 12000 человек.

На военном совете всех генералов отряда было принято решение не штурмовать крепость с ходу, а начать систематическое обложение подступов и полностью перекрыть пути сообщения с Эрзерумом. Инициаторами этого решения выступили В. О. Бебутов и Я. П. Бакланов. Периметр обложения составил 50 верст, но сам характер местности не позволял прикрыть все возможные пути в Карс. В труднодоступных местах были расположены наблюдательные казачьи посты. Уже в самом начале осады Баклановым 18 августа был разгромлен сильный отряд турецких фуражиров, 20 августа отрядом графа Нирода был разбит ещё один фуражирский отряд, наконец, 22 августа была пресечена попытка гарнизона прорвать блокаду. В конце августа из Эрезерума было отправлено подкрепление карсскому гарнизону под командованием Али-паши, общим числом 2500 конницы и несколько сотен пехоты; Муравьёв, оперативно выслал навстречу туркам отряд генерала Ковалевского в составе 7 батальонов пехоты, 1800 кавалерии и 20 орудий. 31 августа у селения Пеняк Ковалевский встретил Али-пашу, причем из Карса к Пеняку сумел прорваться небольшой турецкий отряд, также принявший участие в бою. Турки потерпели поражение, сам Али-паша попал в плен.