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

Началась Турецкая война 1828–1829 годов. Муравьёв командовал Кавказской гренадерской резервной бригадой. Производя и прикрывая постройку первой параллели под Карсом, невольно отвечая на открытый турками огонь, он вовлек в дело все осаждавшие крепость войска. В результате крепость пала, но ещё во время боя главнокомандующий Паскевич, «изумленный нечаянностью, не знающий, что предпринять, не умея сам ничего ни придумать, ни приказать», разразился гневом на Муравьёва и возвышенным голосом спрашивал его: «Что это значило? Кто это приказал? С какого повода сие сделалось без приказания моего? Как смели?» Несмотря на такое отношение, Паскевич, остыв, представил Муравьёва на награждение орденом св. Георгия 4-й степени, причем в реляции были отмечены в хронологическом порядке все подвиги его под Карсом: «В воздаяние ревностной службы и отличия, оказанного в сражениях против турок при осаде и взятии крепости Карса 1828-го года с 20 на 21 число июня, где, при занятии высот на левом фланге нашего лагеря, будучи послан с тремя ротами Эриванского карабинерного полка для вытеснения неприятеля из укрепленных утесов, исполнил поручение сие с примерным мужеством и хладнокровием, так что турки, державшиеся весьма упорно и производившие более часа непрерывный баталионный огонь, были вытеснены и несколько раз, при новых покушениях завладеть тою высотою, опрокинуты с уроном.

С 22 по 23 число со вверенною бригадою, производя и прикрывая постройку первой параллели и батареи 4-й на правом берегу Карс-чая, несмотря на чрезвычайные трудности и неудобства, успел окончить все работы до рассвета и открыть огонь по неприятельским батареям; а в день приступа, при занятии предместья, быв послан с баталионом Эриванского карабинерного полка, для подкрепления, исправляющего должность начальника штаба отдельного Кавказского корпуса, генерал-майора барона Остен-Сакена, во время овладения предместьем Байрам-паша и Карадагом, под сильным картечным огнем с отважностию бросился на неприятеля и овладел батареею из четырех орудий, которые и обратил противу его бастиона».