Также за Ахалцых Муравьёву 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, сделавший на полях её массу отметок, объяснений и замечаний на разные пункты, неоднократно начертал «справедливо».
17 апреля 1848 года Муравьёв был принят вновь на службу с назначением состоять по запасным войскам и 18 апреля прикомандирован к генералу от инфантерии В. И. Тимофееву главным начальником запасных батальонов 3-го, 4-го и 5-го пехотных корпусов. С 13 сентября назначен членом Военного совета и, наконец, с 20 декабря командовал Гренадерским корпусом, с которым выступил к границам Венгрии; 31 мая 1850 года был удостоен ордена св. Александра Невского. Муравьёв постепенно вновь приобретал доверие государя, и 6 декабря 1853 года был произведён в генералы от инфантерии и 29 ноября 1854 года пожалован генерал-адъютантом с назначением наместником Кавказским и командиром Отдельного Кавказского корпуса. Ему предстояло руководить войсками на Кавказском театре Крымской войны.
С назначением Муравьёва «неумолкаемому хабару» (кавказское местное выражение, означающее слово «новость»), догадкам и хитросплетениям не было границ. Одни считали его нелюдимым, каким-то пугалом, чуть не людоедом; другие – человеком с закаленным сердцем, лишенным всяких добрых чувств, а иные – просто устарелым, грубым, не обладающим современными взглядами, необходимыми для высшей административной деятельности, хотя не чуждым высшего образования.
В январе 1855 года Муравьёв прибыл на Кавказскую линию, откуда из крепости Грозной написал А. П. Ермолову письмо, признанное им самим впоследствии нетактичностью; в нём он нелестно отозвался о порядках в армии:
«В углу двора обширного и пышного дворца, в коем сегодня ночую, стоит уединенная, скромная землянка ваша, как укоризна нынешнему времени. Из землянки вашей при малых средствах исходила сила, положившая основание крепости Грозной, покорению Чечни. Ныне средства утроились, а все мало да мало. Деятельность вашего времени заменилась бездействием; тратящаяся ныне огромная казна не могла заменить бескорыстного усердия, внушенного вами подчиненным вашим для достижения предназначаемой вами цели. Казна сия обратила грозные крепости ваши в города, куда роскошь и довольства жизни привлекли людей посторонних. Все переменилось, обстроилось; с настойчивостью и убеждением в правоте своей требуют войск для защиты; войска обратились в горожан, и простота землянки вашей не поражает ослабевших воинов Кавказа, от коих дух хотя и не исчез, но силы стали немощны. Таковое состояние дел, конечно, подало повод и к частным злоупотреблениям начальников. Хотя солдата не грабят, но пользуются трудами его как работою тяглового крестьянина, состояние, которое солдат предпочитает строевой службе. Посудите, какое мое положение. Исправить в короткое время беспорядки, вкоренившиеся многими годами беспечного управления, а в последнее время и совершенным отсутствием всякой власти и управления, – труд великий, поздних последствий которого я не увижу и который доставит мне только нарекание всего населения. Но вы, зная меня, убедитесь, что это меня не останавливает: если не достигну конца, то дам направление сему великому делу, поглощающему силы и кару России. В землянку вашу послал бы их учиться; но академия эта свыше их понятий. Не скажу, чтобы здесь не было покорности; напротив того, здесь все покорны; но покорность эта не приводит их к изучению своих обязанностей, а только к исполнению того, что прикажут. Надобно пока и этим довольствоваться с надеждою на время, которое выкажет сотрудников, ибо дарований здесь встречается более чем в России, но все погрязло в лени и усыплении. От многих слышал я справедливые суждения, что ваша Грозная крепость служила основанием покорения Чечни…»
