Деятельность Н. Н. Муравьева была высоко оценена. 26 августа исторического 1858 года император Александр Николаевич издал указ, который подводил итог личным заслугам генералу – губернатора: «Граф Николай Николаевич! Примерно ревностное и полезное служение нашим, неоднократно ознаменованное военными подвигами и особыми отличиями на поприще гражданского управления, обратили на себя внимание в бозе-почившего родителя моего. Справедливо оценяя ваши достоинства, он вверил начальствованию вашему обширный край в отдаленнейших пределах империи. Вы вполне оправдали доверие одиннадцатилетнему неутомимыми трудами на пользу и благоустройство вверенной управлению вашему Восточной Сибири…Воздаяние за таковые заслуги ваши, я возвел вас указом сего числа Правительствующему Сенату данным, в графское Российской империи достоинство, с присоединением к имени вашему названия Амурского, в память о том крае, которому в особенности посвящены, были в последние годы настоятельные труды ваши и постоянная заботливость».
Таким образом, с 26 августа 1858 года генерал-губернатор Восточной Сибири стал графом Муравьевым-Амурским. Труды его на благо России продолжались.
Вторым приобретением губернатора стал Уссурийский (ныне приморский) край, который он занял, опередив англичан и французов. 2 июля 1859 года губернатор прибыл в южное Приморье на параходе-корвете «Америка», чтобы принять решение, в какой гаване заложить будущий главный порт России на Тихом океане. Осмотрев несколько бухт, он остановил свой выбор на Золотом Роге и сам придумал название будущему городу: Владивосток. Тогда же он посетил залив Америка, где обнаружил удобную бухту, которой дал название Находка. Так что два главных города Приморья обязаны своими звучными и красивыми названиями губернатору Муравьеву-Амурскому.
По инициативе и при активном участии Муравьева-Амурского проведено административно-территориальное преобразование Восточной Сибири, учреждены Забайкальское (1851) и Амурское (1860) казачьи войска, Сибирская флотилия (1856) . При нем основаны многие посты и административные центры на Дальнем Востоке, такие как зимовье Петровское – 1850 г., посты Николаевский, Александровский, Марлинский, Муравьевский – все в 1853 году, Усть-Зейский (Благовещенск) – 1858 год, Хабаровка – 1858 год, Турий Рог – 1859 год, Владивосток и Новгородский – 1860 год. Муравьев-Амурский последовательно проводил переселенческую политику, лично побывал во многих пунктах вверенной ему территории. В том числе на Камчатке. Поход на Камчатку был трудным из-за бездорожья и необжитости района. Но благодаря тщательной подготовке под личным руководством Н.Н. Муравьева Амурского поход закончился успешно. Об этом путешествии достаточно подробно рассказал в своей книге «Воспоминание о Сибири» Б.В. Струве, который в течение 1848-1855 гг. служил в администрации генерал-губернатора. Книга была издана в Санкт-Петербурге в 1889 году, один ее экземпляр хранится в библиотеке Общества изучения Амурского края. Несколько страниц книги посвящены жене Н.Н. Муравьева-Амурского, которая сопровождала его в этой трудной экспедиции на Камчатку.
« Е.Н. Муравьева – родом француженка, урожденная Ришмон, присоединилась к православию при выходе в замужество за Муравьева. Нетрудно ей было убедить своего мужа взять ее с собой на Камчатку, потому что он был в нее влюблен безумно, она поклялась безропотно переносить все трудности предстоявшего путешествия, которые ей рисовались не в розовом свете…
У Меинской станции сели мы на лошадей, даже дамы в мужских костюмах, в высоких сапогах, и вступили в непроходимые тундры и девственные леса, по которым пролегает путь от Якутска до Охотска: 1000 верст и верст старинных екатерининских, семи сотенных. Сколько неимоверных трудностей перенесли мы, сколько казавшимся нам непреодолимыми препятствий побороли мы только благодаря настойчивости, твердости и опытности Муравьева, показывавшего во всем пример. После первого 25-верстного верхового перехода Екатерина Николаевна, будучи разбита до изнеможения, не могла в назначенный час сесть опять на лошадь. Это обстоятельство не было предусмотрено инструкцией, и я ждал приказаний, как быть. В станционном домике, где легла было отдохнуть генеральша, произошел, наконец, крупный разговор по-французски, как мы слышали, стоя тут у входа с оседланными лошадьми. Выходя из избы, Муравьев приказал мне отправить супругу одну с камердинером Флегонтом обратно в Якутск, где ей предоставлялось остаться до возвращения генерала из Камчатки или вернуться в Иркутск.
Муравьев сел на свою лошадь в назначенный по маршруту час и отправился дальше, а Екатерина Николаевна вернулась бы в Якутск, если бы она, убедившись в неуступчивости своего супруга, не сделала сверхъестественное усилие: при помощи моей и Флегонта она поднялась, заливаясь слезами, на свою лошадь и поехала за своим жестоким мужем. Как объяснить эту жестокость? Опытностью: он знал, что если в том разбитом состоянии, в котором находилась его жена, залежаться. То это не пройдет в течение нескольких дней, а если немедленно опять сесть на лошадь и продолжать путь, то эта разбитость пройдет сама собой, незаметно. Без потери времени для дела, в котором каждый день рассчитан».
Представляется необходимым процитировать еще одну редкую книгу, хранящуюся в библиотеке Общества изучения Амурского края, - «Граф Николай Николаевич Муравьев-Амурский по его письмам, официальным документам, рассказам современников и печатным источникам», изданную в 1891 году. Книга содержит интересные сведения о последних годах государственной деятельности графа Н.Н. Муравьева-Амурского в Сибири. В январе 1861 года он сдал свою должность М.С. Корсакову и навсегда покинул край, где им было сделано так много. О том, как сердечно провожали Муравьева-Амурского в Иркутске, вспоминает Б. Милютин: «Назначенный для отъезда день начался в соборе, в котором при архиерейском служении граф Муравьев, окруженный обществом, отстоял напутственный молебен. Площадь, или, лучше сказать, ряд площадей, окаймляющих собор, кишела народом. После молебна все, имевшие на то право. Бросились в близлежащее Собрание. Граф Муравьев дошел до него пешком; народ теснился около него; слышались прощальные крики. Графу приходилось останавливаться, выслушивать прощальные напутствия. Наконец, он в Собрании. Громадная зала, последнего, прилегающие комнаты кишели публикой. Тут были и мундиры, и ремесленники со значками, и фраки, и сюртуки, и крестьяне, прибывшие из соседних деревень, и инородцы, и казаки. Не было, кажется, человека, которому бы граф не сказал слова. Кончилось это прощание. В городских экипажах, кто только мог, поехали на Вознесенский монастырь. Казалось, что туда прибудут только избранные, но пока шел молебен над мощами Святителя Иннокентия, пока продолжался завтрак у настоятеля, площадь перед монастырем наполнялась народом, буквально прибежавшим. Чиновники вынесли по сибирскому обычаю на руках графа Муравьева; но толькопоказались в толпе, как моментально были отброшены в сторону, а граф очутился на руках сперва крестьян, а потом инородцев, поспешно выхвативших его у первых. Им выпало на долю сказать последнее «прости»… «Когда я, - пишет Б. Милютин, - протискался сквозь толпу и подошел к экипажу графа, я слышал только следующие слова, произнесенные инородцами: «Мы тебя, граф, не забудем, не забудь и ты нас»… «Не забудь нас!» – подхватил народ. Тронулись повозки, все стояли без шапок; кто бежал сзади; кто обратился к монастырю и крестился, кто набожно благословлял отъезжавшего. Шибче и шибче двигались повозки. Народ долго еще стоял без шапок, следя за ними. Стоял и я… Невольно пришло в голову: закатывается зорька Восточной Сибири!»
Таким было прощание с Н.Н. Муравьевым-Амурским в январе 1861 года в Иркутске. Покинув Сибирь навсегда, он никогда не порывал с ней связи. Помнили его бывшие сослуживцы, ему писали, с ним советовались по разным вопросам. В январе 1861 года в Петербурге Н. Н. Муравьев-Амурский получил подарок в память о его деятельности в Восточной Сибири. Ему были преподнесены серебряные часы, изготовленные по специальному заказу. Циферблат часов вместо обычных чисел имел надпись: «16-го мая 1858 г.» – дата заключения Айгунского договора.. Над циферблатом два ангела поддерживали герб Н. Н. Муравьев Амурского, здесь же был помещен щит с датой «11-19 января 1851-1854 г.», это были годы первых русских экспедиций на Амур. По обеим сторонам циферблата располагались фигуры казака и китайца, которые символизировали сближение России с Китаем. Около этих фигур были помещены эмблемы зарождающейся деятельности во вновь приобретенных землях (развитие промышленности и торговли, научные исследования и др.).
Массивные часы были окружены барельефами, где изображались первые плавания по Амуру и его лиману, вид Николаевского поста в 1855 году, сцена заключения Айгунского договора, торжественное построение войск в станице Благовещенской. Верхняя часть часов венчалась женской фигурой, олицетворяющей реку Амур. На тыльной стороне часов были выгравированы имена людей, преподносивших этот уникальный подарок (около 200 фамилий).
Часы были установлены на мраморном основании, где помещался маленький орган; он исполнял «Амурский марш» и другие музыкальные пьесы, звучавшие во время первых экспедиций по Амуру. Н.Н. Муравьев-Амурский, получив подарок, был, тронут настолько, что не смог сдержать слез.
Служба его закончилась в феврале 1861 года, он был уволен по прощению и болезни. В рескрипте императора Александра II были отмечены выдающиеся заслуги Муравьева-Амурского в становлении российской государственности в Восточной Сибири и на Дальнем Востоке, он был назначен пожизненным членом Государственного совета.