Когда Н. В. Муравьев занял пост министра юстиции, прошло почти 30 лет с памятного дня утверждения Судебных уставов. Однако «благами» реформы пользовались в России далеко не все. 23 губернии и области, в том числе обширные территории Сибири, Степного и Туркестанского краев продолжали жить по дореформенным судебным порядкам. Наиболее были подготовлены к открытию новых судов Олонецкая, Оренбургская и Уфимская губернии. Этим Муравьев и занялся. В мае и июне 1894 года он лично открыл суды в этих губерниях, а заодно ближе познакомился и с судебными деятелями, которым предстояло проводить в жизнь реформу.

Меры по улучшению правосудия в обширном Сибирском крае принимались еще с 1885 года. Однако ожидаемых успехов достигнуто не было. Муравьев, тщательно изучив состояние судебной части в Сибири, пришел к твердому убеждению, что никакие частные изменения здесь не помогут. Необходимо было все изменить коренным образом на началах Судебных уставов 1864 года, приспособив их к местным условиям. Открытие Иркутской судебной палаты состоялось 2 июля 1897 года в присутствии Н. В. Муравьева.

К концу XIX века были открыты также новые судебные установления в Туркестанском крае, Степных и Закаспийских областях Российской империи, затем в северо-восточных уездах Вологодской губернии. 1 июля 1899 года на имя Муравьева был дан высочайший рескрипт, в котором отмечалось: «В вас, как в Министре юстиции, Я нашел отменно деятельного, даровитого и всесторонне подготовленного исполнителя Моих предначертаний. Сегодня, когда за введением Судебных уставов в северо-восточных уездах Вологодской губернии, на пространстве России нет уже более местности, которая бы не пользовалась благами присущих сим Уставам вечных начал правды, милости и равенства всех перед законом, Я с чувством живейшего удовольствия выражаю вам душевную Мою признательность за оказанное вами многополезное сотрудничество».

Вступив в должность министра юстиции, Н. В. Муравьев начал грандиозную работу по пересмотру законодательства по судебной части. За 30 лет со дня их введения было разновременно принято уже около 700 различных законов, в той или иной степени изменяющих, дополняющих, а то и вовсе ликвидирующих некоторые статьи уставов. Все это мешало практическим работникам, вносило путаницу, и даже опытные юристы иногда с трудом продирались сквозь законодательные дебри. Комиссия под председательством Муравьева работала пять лет. В результате были подготовлены новые редакции Учреждения судебных установлений, уставов гражданского и уголовного судопроизводства, включающих в себя около 4,5 тысячи статей. Однако в связи с надвигавшейся войной с Японией, а затем и обострением революционной ситуации, они так и не были приняты.

Начало ХХ века Н. В. Муравьев встретил в расцвете своей славы. К этому времени он имел чин действительного тайного советника, был награжден многими высшими орденами Российской империи. В России резко обострилась обстановка, один за другим совершались террористические акты на высших царских сановников. Революционеры готовили покушение и на Муравьева. Усиливалась и репрессивная направленность деятельности правительства. В такой ситуации Николай Валерианович не посчитал возможным оставаться далее на посту министра юстиции и генерал-прокурора. Он попросил об отставке. В конце 1904 года Муравьев стал усиленно добиваться места посла в Париже, но такой возможности ему не представилось. Однако вскоре посол в Риме князь Урусов был переведен в Вену, а на открывшуюся вакансию назначен Н. В. Муравьев.

Николай Валерианович выехал для работы в Рим. Он занимался дипломатическими делами с такой же энергией, как и в министерстве.

Н. В. Муравьев был женат три раза. Последней его женой была Евгения Ивановна Аккерман — женщина волевая, державшая Муравьева «в большом респекте».