Полное обложение Карса русскими войсками завершилось к концу июля 1855 года. В начале сентября между Муравьёвым и Баклановым начались серьёзные разногласия. Муравьёв был настроен начинать штурм крепости, Бакланов был категорически против, утверждая что разведка крепостных укреплений проведена неудовлетворительно, в имеющихся картах есть многочисленные ошибки и неточности. На этом основании Бакланов утверждал, что при штурме русские войска понесут неоправданно высокие потери при полной неопределенности исхода штурма. Однако Муравьёва переубедить не удалось. Штурм был назначен на раннее утро 17 сентября. Накануне выяснилось, что турки откуда-то узнали о русских планах и готовы отразить штурмующих. Бакланов сделал последнюю попытку переубедить Муравьёва, тот был непреклонен. Штурмующие колонны были встречены сильнейшим артиллерийским огнём, тем не менее генералам Базину и Бакланову удалось один за другим взять три редута, им оставалось взять лишь форт Вели-Табия. Оба генерала тщетно просили у Муравьёва подкреплений, но тот был вынужден бросить весь резерв на выручку колонны генерала Майделя, гибнущей под фортом Шорах. Севернее Шораха, у Чахмахских укреплений, огромные потери понесла колонна генерала Ковалевского, сам Ковалевский был убит. Муравьёв был вынужден скомандовать общее отступление. По официальным данным потери убитыми и ранеными среди русских войск составили 4 генерала (1 убит), 250 офицеров (74 убито) и более 7000 нижних чинов (убито около 2300 человек). Потери обороняющихся исчисляются в 1400 человек убитыми и ранеными.

На следующий день после неудачного штурма на военном совете было принято предложение Бакланова брать Карс измором. Несмотря на крайне уязвлённое самолюбие, Муравьёв примирился с Баклановым, хотя нрав у обоих был весьма тяжёлым и неуживчивым, да и сам Бакланов никак не мог заставить себя соблюдать субординацию. К чести Муравьёва, он не упал духом и твёрдой рукой продолжал руководить осадным корпусом.

Из грузинских, армянских и азербайджанских добровольцев был организован большой партизанский отряд под командованием М. Т. Лорис-Меликова, действующий на дальних коммуникациях турок и пресекающий попытки доставить продовольствие осаждённым. В крепости начался голод, жители разбегались по окрестностям, началось дезертирство. Русские войска не препятствовали выходу из крепости безоружных, но жёстко пресекали любые попытки обратного проникновения. 12 ноября начались переговоры о сдаче, 14 ноября 1855 года карсский командующий Вассиф-паша подписал полную капитуляцию крепости. Муравьёв был 4 декабря 1855 года награждён орденом св. Георгия 2-й степени № 97 «За взятие крепости Карса 16 ноября 1855 года» и удостоен приставки к фамилии «Карсский».

22 июля 1856 года Муравьёв был уволен от занимаемой должности с назначением членом Государственного совета, 9 декабря 1858 года Муравьёв был назначен председателем Генерального военного суда над лицами, виновными в беспорядках и злоупотреблениях по снабжению войск бывших Крымской и Южной армий предметами довольствия. 9 июня 1859 года Муравьёв был уволен в бессрочный отпуск с сохранением содержания «до излечения болезни».

Короткое наместничество Муравьёва, несмотря на значительный ум этого человека, не оставило заметных следов в истории гражданского управления Кавказом: ни одного сколько-нибудь существенного закона или значительного преобразования за его время проведено не было. Это объясняется отчасти тем, что отвлечённый военными действиями и разъездами по краю, Муравьёв провел в Тифлисе всего около 6 месяцев, отчасти неблагосклонностью к нему молодого государя Александра II, которую Муравьёв чувствовал, с горечью отклоняя все надвигавшиеся проекты «до лучших дней». Неосторожное распоряжение, сделанное им в покоренной Чечне, доставившее, по замечанию императора, «истинное удовольствие Шамилю», вынудило к увольнению Муравьёва от должности. Этому предположению, высказанному в труде «Утверждение Русского владычества на Кавказе», нельзя не верить; военно-исторический отдел при штабе Кавказского военного округа, руководимый таким авторитетом, как покойный В. А. Потто, ревнивый к прошлому, вряд ли допустил ошибку; другой авторитет А. Л. Зиссерман тоже говорит, что Муравьёв «не думал проситься об увольнении», между тем Д. И. Романовский, а также П. Брянчанинов, личный адъютант Муравьёва, свидетельствуют, что Муравьёв просил об увольнении. Вопрос этот спорный, и его не разъясняет рескрипт, хотя нельзя не видеть, что в нём отдается справедливость «воинским доблестям», а по званию наместника – лишь «неутомимому усердию». Прощаясь с войсками, Муравьёв в приказе выражается, что в них «всегда признавал одно из лучших украшений и надежд возлюбленного отечества». Конечно, совершенно справедливо изменил Муравьёв свой взгляд на кавказские войска и, несомненно, пожалел о письме Ермолову, посланном при первоначальном объезде края.

Последние годы своей жизни Муравьёв проживал большею частью в имении Скорняково (Архангельское) Задонского уезда Воронежской губернии (сейчас Липецкая область), причем в 1861 году получил звание второго шефа Самогитского гренадерского полка и зачислен в списки 13-го Лейб-гренадерского Эриванского полка. Подготовил 2-томный труд «Война за Кавказом в 1855 году». Посвящая много забот своему имению, он, между прочим, в 1866 году энергичными мерами приостановил распространение холеры. В этом же 1866 году, 23 октября, он скончался и погребен у восточной стороны Владимирского собора Задонского Богородицкого монастыря, причем похороны, согласно завещанию, отличались необыкновенной скромностью. После смерти оставил обширный дневник, печатавшийся в 70 – 90-х годах в «Русском архиве».

По словам врача Европеуса, «во многом подражая Суворову, покойный Николай Николаевич вел жизнь регулярную, простую, избегая всякой роскоши, к чему приучал и дочерей своих. Спал он обыкновенно в своем кабинете на соломенном тюфяке и таковой же точно подушке, накрываясь шинелью. Вставая довольно рано, он к восьми часам выходил к утреннему чаю в такой же шинели внакидку; так принимал и у себя в кабинете не только своих адъютантов, но и штаб-офицеров, являвшихся к нему по службе. Стол его был русский: сытный и несложный; к обеду подавали, и то не всегда, по бутылке белого и красного вина, но сам Николай Николаевич почти ничего не пил, утоляя жажду простым квасом. К его прибору ставили обыкновенно большой деревянный жбан и при нём ковш. Хотя Николай Николаевич любил нашу русскую баню, был страстный охотник попариться, но нежиться или наслаждаться этим не любил, вообще умея переносить жесточайший холод. В самые трескучие морозы он прогуливался в одном сюртуке за городскую заставу в казармы, и следовавшему за ним офицеру, не имевшему не только фланелевой фуфайки, но, может быть, даже и жилетки, приходилось порядком зябнуть. Муравьёв не любил изнеженных маменькиных сынков и, замечая на ком-либо из офицеров шинель с бобровым воротником, делал замечания, что-де такая шинель – роскошь для солдата, что сам шинели с бобровыми воротниками никогда не нашивал. С каждым являвшимся к нему офицером он долго разговаривал, зондируя его со всех сторон, измеряя степень его знаний, способностей и в то же время расспрашивая испытуемого о его родстве и связях».

Муравьёв был несомненно человек способный, суровый только по наружному виду, а в сущности не злой, но характера мнительного, недоверчивого, своеобразного и невыносимо тяжелого, отчего во время его управления Кавказом произошёл большой застой в делах. Обращался он со всеми без раздражения и без изысканных тонкостей, просто, иногда не без острот и поступал порой оригинально. Так, будучи недоволен комендантом и полицеймейстером Тифлиса, он первому назначил прибыть к 9 часам утра на гауптвахту, куда обещал приехать, но лишь в 10 часов вечера дал знать, что не будет, заставив просидеть напрасно полдня, а второго принял в бане, где парился, откуда полицмейстер вышел мокрым. Твердой воли и строгий к самому себе, Муравьёв был столь же строг и к подчиненным. Считая, что ревностное исполнение служебного долга не является чем-либо особенным, он был скуп на награды, почему его отличия сделались лучшей рекомендацией. Прямолинейность и резкость характера создали ему множество врагов. Муравьёв не любил безделья и, когда утомлялся, то, в виде отдыха, учил дочерей вести счёты по домашнему хозяйству и по имению.