21 ноября 1819 года Муравьёв отправился в обратный путь и 13 декабря прибыл на каспийское побережье. Вслед за ним, 17 декабря прибыло посольство хивинского хана. На следующий день экспедиция с хивинскими и туркменскими посланниками на борту отплыла в Баку, и на рассвете 24 декабря корабли бросили якорь на Бакинском рейде. В январе 1820 года Муравьёв и Пономарёв прибыли в Тифлис и представили Ермолову свои отчёты. Путешествие закончилось. За отличное выполнение этого поручения Муравьёв 4 мая 1820 года был произведён в полковники.
С марта 1821 года по январь 1822 года Муравьёв вторично совершил экспедицию на восточное побережье Каспийского моря. За эту экспедицию получил 3 сентября 1822 года орден св. Владимира 3-й степени.
Свои впечатления от поездок в Среднюю Азию он изложил в книге «Путешествие в Туркмению и Хиву» (1822 год), содержащей ценнейшие материалы политического, географического, экономического, этнографического и военного характера. Книга получила известность не только в России, но и в Европе.
По возвращении из Хивы 11 июня 1822 года Муравьёв был назначен командиром 7-го карабинерского, впоследствии 13-го Лейб-гренадерского Эриванского полка. С ним он участвовал в Персидской войне, в кампании 1826 года, оперируя в глубине Персии, а в кампании 1827 года, будучи помощником начальника штаба отдельного Кавказского корпуса, принимал участие в осаде и взятии крепости Аббас-Абада и в делах против наследника персидского престола Аббас-Мирзы, в том числе был при занятии крепости Меренда и города Тавриза. За отличие в кампании Николай Николаевич 2 октября 1827 года получил алмазные знаки к ордену св. Анны 2-й степени и 15 марта 1828 года был произведён в генерал-майоры.
Оставаясь добросовестным в служебных делах, он по-прежнему сохранял верность идеалам свободолюбия, даже образовал офицерское общество «вольнодумцев», о чем Ермолов знал, но не обращал на это внимания. Боевая служба на Кавказе у Ермолова способствовала тому, что Муравьёв и его единомышленники избежали участи декабристов в Петербурге в 1825 года. На Кавказе Николай Николаевич женился на Софье Ахвердовой, дочери тифлисского генерала, Ермолов был на свадьбе посаженным отцом.
Началась Турецкая война 1828–1829 годов. Муравьёв командовал Кавказской гренадерской резервной бригадой. Производя и прикрывая постройку первой параллели под Карсом, невольно отвечая на открытый турками огонь, он вовлек в дело все осаждавшие крепость войска. В результате крепость пала, но ещё во время боя главнокомандующий Паскевич, «изумленный нечаянностью, не знающий, что предпринять, не умея сам ничего ни придумать, ни приказать», разразился гневом на Муравьёва и возвышенным голосом спрашивал его: «Что это значило? Кто это приказал? С какого повода сие сделалось без приказания моего? Как смели?» Несмотря на такое отношение, Паскевич, остыв, представил Муравьёва на награждение орденом св. Георгия 4-й степени, причем в реляции были отмечены в хронологическом порядке все подвиги его под Карсом: «В воздаяние ревностной службы и отличия, оказанного в сражениях против турок при осаде и взятии крепости Карса 1828-го года с 20 на 21 число июня, где, при занятии высот на левом фланге нашего лагеря, будучи послан с тремя ротами Эриванского карабинерного полка для вытеснения неприятеля из укрепленных утесов, исполнил поручение сие с примерным мужеством и хладнокровием, так что турки, державшиеся весьма упорно и производившие более часа непрерывный баталионный огонь, были вытеснены и несколько раз, при новых покушениях завладеть тою высотою, опрокинуты с уроном.
С 22 по 23 число со вверенною бригадою, производя и прикрывая постройку первой параллели и батареи 4-й на правом берегу Карс-чая, несмотря на чрезвычайные трудности и неудобства, успел окончить все работы до рассвета и открыть огонь по неприятельским батареям; а в день приступа, при занятии предместья, быв послан с баталионом Эриванского карабинерного полка, для подкрепления, исправляющего должность начальника штаба отдельного Кавказского корпуса, генерал-майора барона Остен-Сакена, во время овладения предместьем Байрам-паша и Карадагом, под сильным картечным огнем с отважностию бросился на неприятеля и овладел батареею из четырех орудий, которые и обратил противу его бастиона».
После Карса, Н. Н. Муравьёв под началом Паскевича участвовал в сражениях под Ахалцыхом и последующем взятии этой крепости, был в боях при селении Чаборий и взятии там укреплённого турецкого лагеря (за отличие награждён 27 января 1830 года орденом св. Анны 1-й степени), при селении Каинля, при занятии Эрзерума и Байбурта; за взятие последнего пункта был награждён 21 апреля 1830 года орденом св. Владимира 2-й степени. За участие во взятии крепости Ахалцыха и в других делах был 1 января 1829 года награждён орденом св. Георгия 3-й степени. Его подвиг описан так. «В воздаяние отличия, оказанного в сражениях против турок при покорении крепости Ахалцыха в 1828 году, начальствуя первою линией пехоты, с отличным благоразумием и распорядительностию вел оную 5 августа в действие; когда же неприятель атаковал наш правый фланг, то с двумя баталионами Эриванскаго карабинернаго полка мужественно остановил его стремление, отбил от батареи и причинил ему большой урон; 9-го числа, начальствуя войсками в лагере оставшимися, сделал с двумя баталионами весьма полезное движение к неприятельскому лагерю и, соединясь с войсками, посланными для овладения оным, повел упомянутые баталионы на приступ».
Также за Ахалцых Муравьёву 21 апреля того же года была пожалована золотая шпага с надписью «За храбрость». Когда после окончания войны Паскевич стал изгонять из войск «ермоловский дух», в числе уволенных с Кавказа генералов и офицеров оказался и Николай Николаевич. К этому несчастью добавилось новое: в 1830 году умерла при родах жена Муравьёва, и на его руках осталась малолетняя дочь.
Прожив некоторое время в деревне Осташево под Москвой, у отца, Муравьёв обратился с просьбой о восстановлении его на военной службе к начальнику Главного штаба И. Дибичу и вскоре получил назначение командиром гренадерской бригады 6-го пехотного (бывшего Отдельного Литовского) корпуса. С нею он участвовал в усмирении польского восстания 1831 года, в том числе в штурме Варшавы, где судьба вновь свела его с Паскевичем, руководившим русскими войсками. За отличия при штурме Варшавы получил чин генерал-лейтенанта и был назначен начальником 24-й пехотной дивизии. Позже, 21 июля 1832 года получил польский знак «Virtuti militari» 2-й степени.
В том же 1832 году Николай Николаевич был командирован в Александрию к наместнику Египта Мегмет-Али с Высочайшим требованием прекратить военные действия против Турции и помириться с султаном Махмудом II. Эта командировка была вызвана следующими обстоятельствами. Египет, составляя нераздельную часть Турции, управлялся чиновником со званием наместника султана. В 1832 году Мегмет-Али возмутился против своего повелителя и потребовал отделения от Турции Египта с Сирией и некоторыми приморскими городами. Тогда султан обратился за помощью к императору Николаю I. Николай I, в свою очередь, стремился изменить положения Адрианопольского договора (1829 года) в более выгодную для России сторону и с этой целью послал Муравьёва сначала в Константинополь. Затем Муравьёв приехал в Египет. Мегмет-Али при свидании с Муравьёвым заявил, что беспрекословно исполняет волю государя, и приказал приостановить немедленно военные действия. Едва Муравьёв уехал из Александрии, как Мегмет-Али возобновил военные действия. Сын Мегмета-Али Ибрагим-паша в битве при Конии 21 декабря 1832 года разбил турецкие войска и взял в плен сераскира Решид-Мегмет-пашу со всем штабом. Тогда из Крыма отплыла эскадра адмирала Лазарева с 10000 отрядом, которая 8 февраля 1833 года прибыла в Буюк-Дере и поступила под общее начальство Муравьёва, находившегося в Константинополе. Эскадра Лазарева состояла из 4 линейных кораблей и 5 фрегатов, на берег был высажен десант из нескольких казачьих сотен и двух пехотных полков с артиллерией. Однако это не отрезвило Ибрагима-пашу, который поспешил захватить Смирну. Тогда к Муравьёву были посланы подкрепления. Вскоре туда прибыл чрезвычайный посол и главнокомандующий сухопутными и морскими силами граф А. Ф. Орлов, после чего Муравьёв остался командующим сухопутным отрядом русских и турецких войск, расположившихся биваком на Босфоре в окрестностях Бейкоса. Все дипломатические дела проводил Орлов, встретившийся с Ибрагимом и убедивший последнего увести свои войска за Тавр, Ибрагим-паша подписал с Махмудом II мир. Русские войска простояли на Босфоре до 16 июня, когда после подписания между султаном и Орловым Ункиар-Искелесского договора, отплыли на родину. Муравьёв, на основе материалов поездки подготовил труды «Турция и Египет в 1832 и 1833 годов», «Русские на Босфоре в 1833 году».
