Началась Турецкая война 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 году».

В 1833 году, 1 июля, Муравьёв был пожалован в генерал-адъютанты, 3 апреля 1834 года назначен исполняющим дела начальника штаба 1-й армии (30 июня был награждён орденом Белого Орла), а 9 июля 1835 года – командиром 5-го армейского корпуса. Командовал корпусом Муравьёв два года и вышел в отставку после выраженного ему Николаем I неудовольствия за смотр. Многие полагают, что якобы государь отнесся строго к Муравьёву, помня, как был им побежден на Красносельских манёврах 1835 года.

Ещё в 1834 году Муравьёв составил записку «О причинах побегов и средствах к исправлению недостатков армии». Цель и содержание записки Муравьёв объясняет в своем дневнике: «…я составил записку, в коей изложил горестное состояние, в коем находятся войска в нравственном отношении. В записке сей были показаны причины упадка духа в армии, побегов, слабости людей, заключающиеся большею частью в непомерных требованиях начальства в частых смотрах, поспешности, с коею старались образовать молодых солдат, и, наконец, в равнодушии ближайших начальников к благосостоянию людей, им вверенных. Тут же излагал я мнение свое о мерах, которые бы считал нужными для поправления сего дела, погубляющего войска год от году. Я предлагал не делать смотров, коими войска не образуются, не переменять часто начальников, не переводить (как ныне делается) людей ежечасно из одной части в другую и дать войскам несколько покоя». Записка заключала несомненно много ценных указаний, и даже император Николай I, сделавший на полях её массу отметок, объяснений и замечаний на разные пункты, неоднократно начертал «справедливо».