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