Та же газета через пять номеров дала еще одно сообщение о событиях на Дальнем Востоке: «Государь император, по всеподданнейшему докладу Его Императорского Высочества Великого Князя генерал-адмирала, соображений генерал-губернатора Восточной Сибири об особенной важности местоположения Усть-Зейской станицы, находящейся при впадении реки Зеи в Амур, названной генерал-губернатором по случаю закладки в ней 9 мая храма во имя Благовещения Пресвятой Богородицы "Благовещенскою станицею", — в 5-й день июля сего года Высочайше повелеть соизволил: учредить в этом месте город, назвав его "Благовещенск"». И добавим — в память о благой вести для России.
26 августа того же года император всероссийский Александр Николаевич издал следующий указ, на этот раз подводящий итог личным заслугам Н. Н. Муравьева: «Граф Николай Николаевич! Примерно ревностное и полезное служение ваше, неоднократно ознаменованное военными подвигами и особыми отличиями на поприще гражданского управления, обратили на себя внимание в Бозе почившего родителя моего. Справедливо оценяя ваши достоинства, Он вверил начальствованию вашему обширный край в отдаленнейших пределах империи. Вы вполне оправдали доверие одиннадцатилетними неутомимыми трудами на пользу и благоустройство вверенной управлению вашему Восточной Сибири [...] В воздаяние за таковые заслуги ваши, Я возвел вас указом, сего числа Правительствующему Сенату данным, в графское Российское империи достоинство, с присоединением к имени вашему названия Амурского, в память о том крае, которому в особенности посвящены были в последние годы настоятельные труды ваши и постоянная заботливость».
Тем же указом одновременно с возведением Н. Н. Муравьева в графское достоинство он был награжден чином генерала от инфантерии. В том же историческом 1858 г. был подписан еще один указ, после чего и появилось на картах Приморье.
В заключении Айгунского договора вместе с Муравьевым-Амурским участвовали также обер-квартирмейстер подполковник Константин Фадеевич Будогоский, показывавший во время переговоров на картах все земли, которые отходили к России, и Яков Парфельевич Шишмарев, переводчик с маньчжурского языка. К. Ф. Будогоский и возглавил экспедицию, которая по горячим следам была организована Сибирским отделом Русского географического общества для исследования новых земель. Вместе с ним в самом начале 1859 г. на Уссури выехали два астронома — поручик А.Ф. Усольцев и капитан П. А. Гамов, топограф капитан А. И. Елец, художник академик А. А. Мейер, переводчик Я. П. Шишмарев, а также три отделения съемщиков. Цели и задачи экспедиции были предельно ясны: съемка демаркационной линии, а также побережья Японского моря, и составление подробной карты Приморья.