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