На Кавказе

Произведённый 7 марта 1816 г. в штабс-капитаны Муравьёв 29 июля того же годы был прикомандирован к командиру отдельного Грузинского корпуса А. П. Ермолову и был послан для осмотра российско-персидской границы; 30 августа 1816 г. произведён в капитаны. В 1817 г. он отправился в составе чрезвычайного посольства в Персию, а по окончании миссии остался на Кавказе и через три года совершил труднейшую экспедицию к восточным берегам Каспийского моря и в Хиву.
Путешествие в Хиву

В 1819 г. было принято решение снарядить экспедицию из Баку к восточному берегу Каспийского моря, среди задач экспедиции было: составление географического описания берегов, разведка полезных ископаемых, изучение возможных путей в Индию и положение начала торговых и дипломатических отношений с туркменами, в видах было также предпринять попытку проникновения в Хиву. Главой экспедиции был назначен Елизаветпольский окружной начальник майор Пономарёв, капитан Муравьёв был придан ему как офицер Генерального штаба. Для экспедиции было назначено два судна: корвет «Казань» и шкоут «Св. Поликарп». 24 июля 1819 г. экспедиция отправилась в путь и 28-го прибыла к туркменским берегам. В течение полутора месяцев обследовалось побережье, Муравьёв проводил всё время в поездках в глубь земли и переговорах со старейшинами туркмен-иомудов. 19 сентября Муравьёв в сопровождении нескольких проводников, денщика и отрядного переводчика-армянина отправился вдоль Узбоя и Южного чинка Устюрта в Хиву. Во время пути проводники всем встречным показывали Муравьёва как пленного русского офицера. 5 октября Муравьёв со спутниками прибыли на хивинскую границу и тот час дали знать ханским чиновникам о своём появлении. Посольству было назначено дожидаться приёма в крепостце Иль-Гельды. Более месяца Муравьёв был заперт в крепости не имея никакой возможности подать вести на каспийский берег о своём положении и не получая никаких вестей от Пономарёва. Только 7 ноября туркменские посыльные сумели доставить ему письмо начальника экспедиции, на которое был написан и также тайно отправлен ответ. Утром 16 ноября было, наконец, получено приглашение хана приехать в Хиву и 17 ноября Муравьёв въехал в пределы одного из самых известныхи таинственных городов Средней Азии. В тот же день Муравьёва посетили высшие чиновники ханства — начальник таможен, первый визирь и диван-беги (верховный судья). 20 ноября состоялась аудиенция у хана, хану были вручены подарки от Ермолова, которыми тот остался доволен. Переговоры с ханом прошли , разногласия вызвало только обсуждение по каким путям должны двигаться торговые караваны к Каспийскому морю.
Муравьёв предложил заключить военный союз и организовать совместную охрану караванов, но хан решил отложить решение этого вопроса до прибытия своего посольства на Кавказ.
21 ноября Муравьёв отправился в обратный путь и 13 декабря прибыл на каспийское побережье. Вслед за ним, 17 ноября прибыло посольство хивинского хана. На следующий день экспедиция с хивинскими и туркменскими посланниками на борту отплыла в Баку и на рассвете 24 декабря корабли бросили якорь на Бакинском рейде; в январе 1820 г. Муравьёв и Пономарёв прибыли в Тифлис и представили Ермолову свои отчёты. Путешествие закончилось. За отличное выполнение этого поручения Муравьёв 4 мая 1820 г. был произведён в полковники.
По результатам поездки в Хиву Муравьёв в 1822 г. в Москве напечатал двухтомные записки о своём путешествии, содержащие ценнейшие материалы политического, географического, экономического, этнографического и военного характера.
С марта 1821 г. по январь 1822 г. вторично совершил экспедицию на восточное побережье Каспийского моря. За эту экспедицию получил 3 сентября 1822 г. орден св. Владимира 3-й степени.
Первый штурм Карса
Штурм Карса в 1828 году

По возвращении 11 июня 1822 г. назначен командиром 7-го карабинерского, впоследствии 13-го Лейб-гренадерского Эриванского полка. С ним Муравьёв участвовал в Персидской войне, в кампании 1826 г. оперируя в глубине Персии, а в кампании 1827 г., будучи помощником начальника штаба отдельного Кавказского корпуса, принимал участие в осаде и взятии крепости Аббас-Абада и в делах против наследника персидского престола Аббас-Мирзы, в том числе был при занятии крепости Меренда и города Тавриза. За отличие в кампании Муравьёв 2 октября 1827 г. получил алмазные знаки к ордену св. Анны 2-й степени и 15 марта 1828 г. был произведён в генерал-майоры.

Началась Турецкая война 1828—1829 гг., где командовал Кавказской гренадерской резервной бригадой. Муравьёв, производя и прикрывая постройку первой параллели под Карсом, невольно отвечая на открытый турками огонь, вовлек в дело все осаждавшие крепость войска. В результате крепость пала, но ещё во время боя главнокомандующий Паскевич, «изумленный нечаянностью, не знающий, что предпринять… не умея сам ничего ни придумать, ни приказать», разразился гневом на Муравьёва и возвышенным голосом спрашивал его: «Что это значило? Кто это приказал? С какого повода сие сделалось без приказания моего? Как смели?» Несмотря на такое отношение, Паскевич, остыв, представил Муравьёва на награждение орденом св. Георгия 4-й степени (№ 4178, 16 ноября 1828 г.), причем в реляции были отмечены в хронологическом порядке все подвиги его под Карсом.