Военную службу Муравьёв начал 9 февраля 1811 года колонновожатым в свите Его Императорского Величества по квартирмейстерской части. Отличные его познания в математике обратили на себя внимание князя П. М. Волконского, который по производстве Муравьёва в прапорщики (13 апреля 1811 года) командировал его в качестве экзаменатора в Корпус инженеров путей сообщения, а затем поручил ему преподавание геометрии в математических классах при чертежной канцелярии Свиты Его Величества. За этот же год он был смотрителем вновь открытого Училища колонновожатых, а также заведующим библиотекой и временами исполнял обязанности адъютанта князя Волконского. До начала Отечественной войны Муравьёв увлекался масонством и совместно с Муравьёвым-Апостолом, Перовским и другими лицами выработал устав тайного общества, которое называлось «Юношеское собратсво», члены которого мечтали об основании на Сахалине республики. Война с Наполеоном положила навсегда предел этим мечтам.

С марта 1812 года Муравьёв состоял при Главной квартире под начальством генерал-квартирмейстера С. А. Мухина, при начале войны был назначен в корпус великого князя Константина Павловича, а при отъезде цесаревича из армии и расформировании его штаба – в главную квартиру под начальство генерала Толя и принял участие в Бородинской битве, за отличие в ней получил 10 сентября орден св. Анны 4-й степени. По оставлении французами Москвы Муравьёв поступил в отряд генерала Милорадовича, и, состоя при нем до конца кампании, принимал участие во многих славных делах Отечественной войны, среди которых выделяются сражения при Тарутино и Вязьме. Когда французская армия отступила за реку Березину, именно Муравьёву поручили наведение моста для переправы русских войск. Работая наравне с подчиненными на холоде, Муравьёв тяжело заболел и вынужден был оставить армию, когда та находилась в Вильне. Вернулся в строй он только в апреле 1813 года, нагнав русские войска в Дрездене. В Заграничном походе Муравьёв принял участие во многих сражениях: при Лютцене, Бауцене, Дрездене, Кульме. За отличие 15 сентября 1813 года удостоен ордена св. Владимира 4-й степени с бантом и 26 сентября произведён в подпоручики. За отличие в битве при Лейпциге 4 октября 1813 года произведён в поручики, при Фер-Шампенуазе (за отличие награждён 28 мая 1814 года орденом св. Анны 2-й степени) и, наконец, был при взятии Парижа, состоя в этот период при генерал-майоре Куруте.

После войны Николай Николаевич стал офицером генерального штаба. Обладая не только боевым опытом, но и высокой образованностью, он подготовил и издал «Курс фортификации». По-прежнему он оставался «вольнодумцем», был очень близок к будущим декабристам. 1816-й год внес перелом в его судьбу, неудачное сватовство к дочери адмирала Н. Мордвинова (тот не захотел брать в зятья скромного офицера) подтолкнуло его отправиться на Кавказ к генералу Ермолову, хорошо знавшему Муравьёва по Отечественной войне. Сначала он сопровождал командира Кавказского корпуса Ермолова в дипломатической поездке в Персию, затем служил у него корпусным квартирмейстером.

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

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 года. На Кавказе Николай Николаевич женился на Софье Ахвердовой, дочери тифлисского генерала, Ермолов был на свадьбе посаженным отцом.