Николай Николаевич принял участив в Заграничном походе русской армии, сражался под Лютценом и Бауценом, Кульмом и Лейпцигом, Фер-Шампенуазом и Парижем, получил несколько боевых наград и закончил войну в звании поручика. Его приняли на службу в Генеральный штаб, но отказ отца невесты знаменитого адмирала Н. С. Мордвинова выдать дочь за небогатого офицера вынудил Муравьева покинуть столицу и искать продвижения на Кавказе, где шла война с горцами. Там Николай Николаевич вновь встретился с Ермоловым, которого знал еще в годы Отечественной войны. На мемуарах Муравьева лежит неизгладимый отпечаток рассказов «проконсула» Кавказа, вплоть до похожего описания некоторых «фронтовых» эпизодов.
Муравьев сопровождал Ермолова в дипломатической поездке в Персию, затем служил у него корпусным квартирмейстером, а в 1819 г. был командирован в Среднюю Азию. За эту миссию Николай Николаевич получил чин полковника. Его книга «Путешествие в Туркмению и Хиву», написанная в 1822 г., была переведена на немецкий, английский и французский языки и издана за рубежом. Тогда же Муравьев получил в командование 7-й карабинерный полк, что существенно поправляло его материальное положение, и вскоре женился на генеральской дочери Софье Ахвердовой. Ермолов был на их свадьбе посаженным отцом.
События на Сенатской площади не прошли мимо семьи Муравьевых. Под следствием оказался брат Александр. Сам Николай Николаевич не пострадал и даже не привлекался к делу, хотя на него как на участника ранних организаций показал С. П. Трубецкой. Однако офицеры, служившие у Ермолова на Кавказе, практически не подверглись гонениям. Сам командующий как будто знал о тайных обществах, но не считал нужным их замечать.
В 1826–1828 гг. Муравьев принял участие в войне с Персией, а 1828–1829 гг. – с Турцией. Совершил дипломатическую миссию в Египет и Турцию, много сделал для заключения Ункяр-Искелесийского мирного договора 1833 г. Однако через три года Николай Николаевич был уволен со службы: у него не сложились отношения с новым командующим на Кавказе И. Ф. Паскевичем, который по возможности избавлялся от «людей Ермолова» в своем корпусе. Муравьеву припомнили и связи с политическими заключенными, и покровительство сосланным декабристам. Только в 1848 г. он сумел вернуться на службу, был назначен командиром гренадерского корпуса, участвовал в походе в Венгрию в 1849 г., при этом одобряя действия венгерских революционеров и считая союзническую помощь Австро-Венгрии «позорной» и ошибочной со стороны России.