В 1873 он занял аналогичную должность в Москве. Прослужив здесь пять лет, Николай Валерианович завоевал славу лучшего обвинителя столицы. Он любил выступать в судебных процессах и умел хорошо их организовывать. Его речи всегда были безукоризненными: юридически обоснованные, грамотные, страстные и красивые, они прочно захватывали внимание слушателей. Одним из самых громких процессов этого периода деятельности Муравьева было дело «Клуба червонных валетов», слушавшееся в Москве в феврале — марте 1877. Суду были преданы за различные преступления 47 человек, объединившихся в шайку. Е. И. Козлинина, присутствовавшая на суде и слушавшая речь прокурора, писала: «Почти два дня длилась эта замечательная речь. Сильная и эффектная, она до такой степени захватывала внимание слушателя, что когда он яркими красками набрасывал какую-нибудь картину, так и казалось, что воочию видишь ее».
В 1874 Н. В. Муравьев выдержал в университете экзамен на степень магистра и стал читать публичные лекции по курсу судебного судопроизводства.
В 1877 Муравьев становится прокурором Ярославского окружного суда, а в январе 1879 переводится в Петербург товарищем прокурора столичной судебной палаты. В 1881 тридцатилетнему прокурору было доверено выступать в Особом присутствии Правительствующего сената по делу «О злодеянии 1 марта 1881 года, жертвою коего стал в бозе почивший император Александр Николаевич». Вскоре после этого процесса Муравьев возглавил столичную прокуратуру. 27 мая 1884 он был назначен прокурором Московской судебной палаты.
В июне 1891 Н. В. Муравьев становится обер-прокурором уголовного кассационного департамента Правительствующего сената, а в следующем году — государственным секретарем. 1 января 1894 он вступил в управление Министерством юстиции, а 17 апреля Николай Валерианович утверждается в должности министра юстиции и генерал-прокурора.
14 января 1905 Н. В. Муравьев был освобожден от обязанностей министра юстиции и назначен чрезвычайным и полномочным послом в Риме.
Н. В. Муравьев скончался 1 декабря 1908; похоронен на кладбище Тестаччио в Риме.
На посту министра юстиции и генерал-прокурора полнее всего раскрылись выдающиеся способности этого «талантливейшего из прокуроров», но, к сожалению, проявились и его негативные качества: властолюбие, нетерпимость к чужому мнению, склонность к внешним эффектам.
Н. В. Муравьев проделал грандиозную работу по пересмотру законодательства по судебной части. Ведь за время действия Судебных уставов было принято около 700 законодательных актов в той или иной степени дополняющих, а то и вовсе ликвидирующих некоторые статьи уставов. Все это мешало практическим работникам, вносило путаницу, так что даже опытные юристы с трудом продирались сквозь законодательные дебри. Комиссия под председательством Муравьева подготовила новые редакции уставов гражданского и уголовного судопроизводства. Однако в связи с революционной ситуацией они так и не были приняты.