В 1826г. Муравьев окончил курс учения первым и с золотой медалью, но по малолетству вышел из корпуса только через год и в 1827 году 17-летним прапорщиком вступил в лейб-гвардии Финляндский полк. Вместе с полком он участвовал и в русско-турецкой войне 1828-1829гг.
С 1828 года Муравьев в чине подпоручика стал адъютантом начальника 19-й пехотной дивизии, генерал-лейтенанта Е.А. Головина. Муравьев был и во время польской компании 1830-1831гг., приобретя в ходе ее первый военно-дипломатический опыт – его не раз посылали с поручениями к польским генералам. «Школа Головина» дала Муравьеву разнообразный опыт и полезные связи.
К середине 1830-х годов материальное положение семейства Муравьевых стало угрожающим. Имениям грозила продажа с публичных торгов. Чтобы спасти положение, Николай Николаевич как старший сын вышел в отставку и поселился в имении Стоклишки в Виленской губернии, но роль сельского хозяина ему не давалась. Лишь младший из братьев, Александр, сумел поправить имущественное положение семьи.
В 1838 году после непродолжительной отставки Н.Н. Муравьев вернулся на военную службу и отправился на Кавказ: в чине майора он поступил для особых поручений к Е.А. Головину, назначенному командиром Отдельного Кавказского корпуса. В1840 году Н.Н. Муравьев стал полковником, начальником отделения Черноморской береговой линии, а в 1841 году, 32-х лет от роду, был «за отличие» произведен в генерал-майоры.
В 1842 году Е.А. Головин покинул Кавказ. Через некоторое время подал прошение об отпуске, ссылаясь на раны и лихорадку, и Н.Н. Муравьев.
В апреле 1844 года Муравьев, молодой (35 лет), полный сил и энергии, заслуженный боевой генерал получил отпуск и поселился в уездном городе Богородицке Тульской губернии, в имении родственника и друга В.И. Муравьева.
После смерти отца в начале 1845 года Н.Н. Муравьев получил продление отпуска и отправился за границу для лечения минеральными водами. По возвращении из-за границы Н.Н. Муравьев был причислен к Министерству Внутренних Дел «...для исполнения поручений, по случаю предполагавшегося назначения его впоследствии в должность военного губернатора, с сохранением военного чина.»7.
Короткий период губернаторства в Туле (менее полутора лет – с июня 1846 года до сентября 1847 года) уже позволяет отметить некоторые черты муравьевского стиля управления.
Свою деятельность новый губернатор начал, как это было принято, с ревизии и объезда губернии. В первом же отчете, указывая на замеченные недостатки, он намечал пути их устранения и пытался найти такие решения, которые позволили бы искоренить сами причины их появления. В Туле же были впервые сформулированы и откровенно проявлены антикрепостнические убеждения Н.Н. Муравьева, в последствии во многом определившие основные направления его деятельности как генерал-губернатора Восточной Сибири.
Во время тульского губернаторства антикрепостнические убеждения Муравьева подвергались весьма серьезному испытанию: в июне 1847 года произошли волнения в имении помещицы Виневского уезда Резвой, потребовавшие его вмешательства. Подобные события не были редкостью в губернии. Но вопреки утверждению исследователя вопроса В.И. Крутикова, тогда дело не дошло до выезда губернатора с военной командой в село и экзекуции6. Действия Н.Н. Муравьева отнюдь не сводились к мерам наказания виновных, а были направлены на предотвращение повторения событий и устранения причин, их вызвавших.
Во время пребывания в Туле Н.Н. Муравьев приобрел не только новый административный опыт, но и некоторых сотрудников, последовавших затем вместе с ним в Восточную Сибирь. Среди них были младший чиновник особых поручений В.И. Бершацкий, исправник Кропивенского земского суда Е.А. Корженевский, бывший домашний учитель сына графа Н.Н. Татищева, ставший чиновником канцелярии тульского губернатора В.В. Гаупт и чиновник особых поручений, а затем старший советник Тульского губернского правления А.О. Стадлер.
С тульским периодом связано еще одно важное событие в жизни Н.Н. Муравьева – он женился. Со своей будущей женой Николай Николаевич познакомился во время поездки за границу в 1846 году. Через год по его вызову она приехала в Петербург, а 19 января 1847 года в городе Богородицке Тульской губернии состоялась свадьба, перед которой Екатерина Николаевна приняла православие. Она принадлежала к дворянскому роду de Richemond (Ришемон) из Лотарингии, но ее родители и родственники жили близ города По на юге Франции. «По свидетельсту знавших Екатерину Николаевну, пишет Барсуков, - она была чрезвычайно красива, умна и образованна. Характера она была мягкого, ровного, добрая сердцем и отличалась любовью к своему новому отечеству. При безграничной любви к жене, Муравьев поддавался ее влиянию, не ослабевшему и в последние годы его жизни, и нельзя не сказать, что, при пылкости характера Муравьева, это влияние было всегда в своих результатах хорошим, подчас умиротворяющим9.
Выбор Н.Н. Муравьева на должность генерал-губернатора Восточной Сибири принадлежал министру внутренних дел Л.А. Перовскому. Провел же он задуманное им дело с помощью Великой Княгини Елены Павловны, оказывавшей постоянно искреннее благорасположение Муравьеву с тех пор, как он был ее камер-пажом. Великая Княгиня, отличавшаяся просвещенным умом и глубоким пониманием современного положения России, которую она любила, как второе свое отечество, видела в Муравьеве именно такого деятеля, каким он оказался впоследствии.
Муравьев оставил Тулу и, в конце сентября 1847 года прибыл в Петербург, где приступил к ознакомлению с тем положением сибирских дел, в котором они находились в то время, и особенно дела об Амуре. По управлению Восточной Сибири стояли тогда на первом плане вопросы о нашем восточном прибрежье на Тихом океане, в связи с деятельностью Северо-Американской Компании, вопросы о кяхтинской торговле и о злоупотреблениях по части золотопромышленности, акцизно-откупного коммиссионерства и провиантских заготовлений. Нужна была настойчивая сила воли Муравьева, чтобы в сравнительно короткое время разобраться в этом хаосе мнений, сведений обо всем этом и предположений об Амуре.
Еще во время пребывания в Петербурге, Муравьев познакомился с капитан-лейтенантом Невельским. Сильно заинтересованный запутанным вопросом доступности для судов устья Амура, Муравьев сообщил Невельскому «свое мнение о необходимости более правильного исследования устья этой реки, где, по словам, сказанным ему Государем, будто бы только трафута глубины при входе.»10. Невельской и сам был сильно заинтересован вопросом об Амуре, поэтому горячо принял заявления Муравьева, и впоследствии он явился деятельным исполнителем указаний Муравьева к осуществлению заветной мысли последнего – завладеть устьями Амура и тем открыть России свободный путь к Тихому океану. Познакомившись, насколько возможно со своею предстоящею деятельностью Николай Николаевич Муравьев выехал в Сибирь.
Первые шаги Н.Н. Муравьева действительно были направлены на то, чтобы «все привести в движение». Энергичные преобразования охватили почти все направления его политики, все области управления. Некоторые из поставленных задач были за это время выполнены, отдельные ориентиры и принципы позже претерпели изменения и были пересмотрены, но многие подходы сохранились надолго. В первую очередь это касается проявившихся уже в первые сибирские годы особенностей стиля и методов управления и таких стратегических целей, как присоединение Амура и расширения сферы компетенции генерал-губернатора. Одной из характерных черт муравьевского стиля управления было умение подчинять всю свою деятельность главной цели. Сама эта цель могла с течением времени и изменятся, на пути к ее достижению могли быть отступления, компромиссы, отвлечения, но приоритет оставался ясен и самому генерал-губернатору, и его ближним подчиненным.
Еще в Петербурге после беседы с императором Муравьев изложил вовсеподданейшем докладе от 8 января 1848 года 12 вопросов, на которые предстояло обратить внимание. В первую очередь: «об обустройстве ссыльных; о частной золотопромышленности; о выгоднейшем для казны устройстве солеварных и винокуренных заводах; о путях сообщения вообще и в особенности около Байкальского озера; о Нерчинских заводах; об устройстве городовых и пограничных казаков; о пограничной нашей линии и сношениях с Китаем; об устранении вредного распространения малайского духовенства в Забайкальском крае; о возможности распространения там православия; об удобнейшем и выгоднейшем сборе ясака; о неудобствах Охотского порта и возможности перенести порт в другое место; о средствах к улучшению сообщений с Охотским морем и Камчаткою»11.
По приезде в Сибирь Муравьев скорректировал эти задачи. В докладной записке на высочайшее имя от 25 февраля 1849 года он писал: «Я нашел здесь весь народ под влиянием и в руках, так сказать, богатых торговцев, промышленников и откупщиков и всех чиновников правительственных, почти без исключения на содержании и в услугах тех же богатых людей. Я строго и твердо принялся действовать против этого направления, ни законами, ни совестью не оправдываемого»12. Таким образом, Муравьев поставил перед собой две взаимосвязанные первоочередные задачи: во-первых, пресечь коррупцию сибирского чиновничества и удалить со службы взяточников, и, во-вторых, ослабить влияние верхушки «торгово-промышленного класса», пресечь двойную и тройную эксплуатацию им народа.
Николай Николаевич Муравьев действовал решительно. В течение первых трех лет им или по его настоянию были отстранены от службы в Восточной Сибири или перемещены на менее значительные места: иркутский губернатор А.В. Пятницкий, председатель Иркутской казенной палаты П.К. Лавриновский, иркутский губернский почтмейстер М.И. Лобковский, управляющий горным отделением ГУВСа К.А. Дейхман (все в 1848г.), сменивший его А.Н. Таскин (1850г.), начальник Нерчинских горных заводов полковник А.Ф. Родственный (1850г.), управляющий Иркутской провиантской конторой военного министерства К.Г. Егоров, бывшие и еще находившиеся на службе адъютанты и чиновники особых поручений прежнего генерал-губернатора К.К. Максимович, Н.М. Яковлев, К.Я. Дараган, П.Н. Успенский и Г.Е. Поменцев. По прсьбе Муравьева был отправлен в отставку бригадный командир генерел-майор В.Н. Щетинин (1849г.)»13. Кроме того, новый генерал-губернатор предложил подать в отставку члену Совета и управляющему его отделением Н.Е. Тюменцеву, но тот отказался это сделать и впоследствии сумел убедить Муравьева в своей незаменимости. Не жалобы и доносы увольняемых и распекаемых чиновников в Петербург, ни дружеский выговор министра Л.А. Перовского не изменили общего курса Муравьева на решительную смену кадров. Но возможности генерал-губернатора в этой, как и в других сферах деятельности, были ограничены, несмотря на широчайшие, казалось бы, полномочия.