В 1884 году Н. В. Муравьева назначили прокурором Московской судебной палаты. Он всегда любил комфорт и лоск во всем: в жизни и в работе. Он сразу же занял роскошную, состоящую из 20 комнат, служебную квартиру в здании судебных установлений в Кремле. С таким же размахом устроил и других служащих прокуратуры. От своих подчиненных Муравьев требовал не только соблюдения строгой дисциплины и ответственного отношения к делу, но и внешней опрятности, достойного поведения. Современники вспоминали, что он в буквальном смысле муштровал прокуроров, особенно придирчиво относясь к наиболее способным из них. Не случайно, лица, прошедшие его суровую школу, быстро продвигались по службе, становились председателями судов, прокурорами палат и окружных судов.
Состав тогдашней московской прокуратуры, хотя и включал много хороших, талантливых сотрудников, не в полной мере удовлетворял требовательного к себе и к сослуживцам прокурора палаты. Твердый, энергичный и решительный, обладавший бойцовскими качествами, Муравьев иногда говорил, что его помощники «не в меру корректны», «недостаточно задиристы», а то и просто «мягки». Поэтому он стремился привлекать в прокуратуру таких обвинителей, как М. Ф. Громницкий, который был настоящей грозой подсудимых.
Н. В. Муравьев всегда стремился привить молодым людям любовь к прокурорской и судебной деятельности. Выступая перед кандидатами на судебные должности, он говорил: «Среди нас больше чиновников судебного ведомства, ремесленников судебной профессии, даже дилетантов судебного дела, чем настоящих судебных деятелей. Многие из нас служат и действуют иногда сами не зная зачем, как придется и машинально, не проникаясь животворным духом нашего дела, не чувствуя к нему любви или даже просто охоты и потому мало заботясь о том, что выйдет из нашей деятельности. А между тем великое дело правосудия требует, кроме специальных познаний и опытности, еще ревностного и сознательного ему служения, которое, в свою очередь, немыслимо без ясного и чуткого разумения, крепкой воли, развитого чувства правды, твердых принципов и стойких убеждений».
Занимался Муравьев и творчеством. Он издал капитальный труд по истории прокурорских органов в России — «Прокурорский надзор в его устройстве и деятельности». Затем опубликовал обширную работу о современной ему прокуратуре — «Общие основания устройства и уголовной деятельности прокурорского надзора».
5 июня 1891 года А. Ф. Кони, занимавший должность обер-прокурора, был назначен Сенатором уголовного кассационного департамента. На освободившееся место министр юстиции Н. А. Манассеин поставил Н. В. Муравьева. Для Николая Валериановича открывались новые перспективы, которыми он не преминул воспользоваться, благодаря поддержке влиятельных лиц при дворе. Впоследствии А. Ф. Кони вспоминал: «Я должен признать, что в новом звании Муравьев был весьма на месте и не уронил его с той высоты, на которую мне удалось его поставить. Его практическая подготовка, умение разобраться в научных материалах и несомненный дар слова нашли себе применение в его заключениях».
Несмотря на несомненные успехи, Муравьев все же «тяготился этой деятельностью и скромным материальным положением». Работа не давала удовлетворения его «ненасытному честолюбию и жадному властолюбию». Кони подмечал, что Муравьев «грыз удила, как скаковой жеребец, поставленный в оглобли закона».
Не прошло и года, как «изнывающий в обер-прокуратуре» Муравьев был назначен государственным секретарем, а обер-прокурором снова стал А. Ф. Кони, соединивший с этой должностью и звание Сенатора.
1 января 1894 года Н. В. Муравьев был поставлен управляющим Министерством юстиции, а 17 апреля того же года утвержден в должности министра юстиции и генерал-прокурора. В то время это был действительно достойнейший кандидат на столь высокий пост. Приведем свидетельство человека, знавшего Муравьева на протяжении длительного времени.
Е. И. Козлинина в своей книге «За полвека» писала: «Но и теперь, когда старые судебные деятели уже стали составлять меньшинство, спросите, кто за все это время был талантливейшим из прокуроров за все эти 45 лет. Вам скажут: Н. В. Муравьев, сначала состоявший в Москве товарищем прокурора, затем, через сравнительно короткий промежуток, уже занимавший пост прокурора судебной палаты, и едва достигнув 46 лет, исключительно благодаря своим выдающимся способностям, занявший пост министра юстиции».
Министром юстиции и генерал-прокурором Н. В. Муравьев оставался 11 лет. На этом посту наиболее полно раскрылись его выдающиеся способности, но и особенно резко проявились его негативные качества: властолюбие, нетерпимость к чужому мнению, резкость и даже грубость, склонность к внешним эффектам, угодничество перед власть имущими, недостаточно высокие нравственные качества.
Желая придать единообразие и стройность системе прокурорского надзора, Муравьев издал в 1896 году Наказ чинам прокурорского надзора судебных палат и окружных судов. В нем впервые подробно и основательно были изложены все основные функции прокуроров при исполнении обязанностей, возложенных на них законом.
Первое время Муравьев использовал свои широкие полномочия с большой осторожностью. Он любил говорить, что работает «на два фронта», так как не хотел ссориться ни с властями, ни с лицами, стоявшими у истоков судебной реформы. Но в дальнейшем, по выражению А. Ф. Кони, он «снял маску» и «стал подкапываться под главные устои нового суда, под суд присяжных, несменяемость судей, единство кассации, предварительное следствие». Все чаще и чаще у него возникали конфликты и трения с независимо держащимися судебными деятелями. В угоду приближенным к императору вельможам требовал от своих подчиненных того или иного решения судебных дел. В таких случаях голосом, не терпящим возражений, он говорил: «На это дело обращено о с о б о е внимание».
В 1895 году Н. В. Муравьев присоединил к Министерству юстиции главное тюремное управление, ранее находившееся в ведении Министерства внутренних дел. Некоторые государственные деятели, например, А. Ф. Кони и С. Ю. Витте, считали такое решение Муравьева серьезной ошибкой.
Когда Н. В. Муравьев занял пост министра юстиции, прошло почти 30 лет с памятного дня утверждения Судебных уставов. Однако «благами» реформы пользовались в России далеко не все. 23 губернии и области, в том числе обширные территории Сибири, Степного и Туркестанского краев продолжали жить по дореформенным судебным порядкам. Наиболее были подготовлены к открытию новых судов Олонецкая, Оренбургская и Уфимская губернии. Этим Муравьев и занялся. В мае и июне 1894 года он лично открыл суды в этих губерниях, а заодно ближе познакомился и с судебными деятелями, которым предстояло проводить в жизнь реформу.
Меры по улучшению правосудия в обширном Сибирском крае принимались еще с 1885 года. Однако ожидаемых успехов достигнуто не было. Муравьев, тщательно изучив состояние судебной части в Сибири, пришел к твердому убеждению, что никакие частные изменения здесь не помогут. Необходимо было все изменить коренным образом на началах Судебных уставов 1864 года, приспособив их к местным условиям. Открытие Иркутской судебной палаты состоялось 2 июля 1897 года в присутствии Н. В. Муравьева.
К концу XIX века были открыты также новые судебные установления в Туркестанском крае, Степных и Закаспийских областях Российской империи, затем в северо-восточных уездах Вологодской губернии. 1 июля 1899 года на имя Муравьева был дан высочайший рескрипт, в котором отмечалось: «В вас, как в Министре юстиции, Я нашел отменно деятельного, даровитого и всесторонне подготовленного исполнителя Моих предначертаний. Сегодня, когда за введением Судебных уставов в северо-восточных уездах Вологодской губернии, на пространстве России нет уже более местности, которая бы не пользовалась благами присущих сим Уставам вечных начал правды, милости и равенства всех перед законом, Я с чувством живейшего удовольствия выражаю вам душевную Мою признательность за оказанное вами многополезное сотрудничество».