Морозы достигли 30°C. Снова холод и голод мучили людей. 9 декабря достигли урочища Кайкукан, где стояли юрты тунгусского племени манегров. Отдохнув немного, отряд отправился в путь на Кутоманду. В Кутоманде стояла небольшая русская команда, которая приютила казаков и вдоволь накормила хлебом. Только 20 декабря, то есть на сороковой день после выхода из Айгуна, казаки добрались до Усть-Стрелки. Дошли все, но в Стрелке умер казак Петр Пешков от гангрены, поразившей обмороженную руку. Этот Пешков, будучи неграмотным, сочинил песню, которую долго потом распевали участники похода:

Он же, Н.П. Беломестнов, описывает удивительный случай силы, воли и выносливости забайкальского казака 5-й Усть-Стрелочной сотни Николая Сурикова:

«Вернувшись с Амура в составе сотни в Кутоманду, отдохнув денек после более трехмесячного изнурительного похода и наевшись вволю хлеба, заявил товарищам, что он дойдет до Усть-Стрелки за два дня. От Кутоманды до Усть-Стрелки 180 верст. Его сочли хвастуном. Однако, отметив время ухода у зауряд-сотника Беломестнова, он через 42 часа был уже в Усть-Стрелке. Время прихода зафиксировал зауряд-сотник Богданов.

Проезжавший летом 1858 года мимо Усть-Стрелки Муравьев узнал об этом случае, вызвал казака Сурикова к себе, поблагодарил за службу, произвел в урядники и поцеловал».

Руководимые умелыми и талантливыми людьми, забайкальцы оказали неоценимую услугу России в освоении своего края и Приамурья.

Направляя конных и пеших казаков для переселения на Амур, Муравьев создал условия окончательного присоединения земель на левом берегу Амура к России. Переселение забайкальцев на Амур осуществлялось добровольно, все права и преимущества, установленные Положением от 17 марта 1851 года, оставались за ними, из списков Забайкальского казачьего войска они не исключались. Кроме того, для переселенцев с Забайкалья на Амур устанавливались дополнительные льготы, способствующие поднятию экономики казачьих общин.

Главным пунктом отправки казаков для жизни и службы на Амуре был Шилкинский завод, где готовились суда и плоты для сплава по Амуру. Переселявшиеся на Амур первые 450 семейств забайкальских казаков должны были заселить огромное пространство от Усть-Стрелки до Хингана.

Был организован и произведен 4-й сплав забайкальцев по Амуру. Китайцы не препятствовали переселению русских на Амур.

В июне 1857 года в штат Забайкальского казачьего войска была введена артиллерия — конно-артиллерийская бригада в составе 2 батарей, имевших номера 23 и 24.

В конце 1857 года Муравьев был назначен генерал-адъютантом, что еще больше упрочило его положение при дворе и в борьбе с царскими министрами за решение Амурского вопроса.

С 11 по 16 мая 1858 года начались переговоры с Китаем об определении границ по Амуру, и 16 мая был подписан Айгунский трактат (договор), названный так по городу, где они проходили.

В этот же день состоялся церковный парад Забайкальских казачьих войск, где генерал-адъютант Н. Муравьев отдал следующий приказ: «Товарищи! Поздравляю вас! Не тщетно трудились мы! Амур сделался достоянием России! Святая православная церковь молится за нас! Россия благодарит. Да здравствует император Александр и процветает под кровом Его вновь приобретенная страна! Ура!» Войска ликовали. 20 мая Муравьев отправил подлинный трактат при своем донесении императору с секретарем по дипломатической части Блютцевым. В донесении указывалось: «Поданному мне… уполномочию я заключил с Амурским главнокомандующим, князем И-Шань договор, который имею счастье здесь в подлиннике повергнуть на… воззрение и утверждение».

На рапорте Муравьева Александр Второй написал: «Слава Богу».

О границе между Россией и Китаем в договоре говорилось: «Левый берег Амура, начиная от реки Аргуни до морского устья реки Амура да будет владением Российского государя, а правый берег, считая вниз по течению до реки Уссури, владением Дайцинского государства (Китая. — Примеч. ред.); от реки Уссури далее до моря находящиеся места и земли, впредь до определения по сим местам границы между двумя государствами, как ныне да будут в общем владении Дайцинского и Российского государств». Было также предусмотрено право совместного пользования реками Амур, Сунгари, Уссури: «…всех же прочих иностранных государств судам по сим рекам плавать не должно». Обязались стороны «для взаимной дружбы» покровительствовать «на обоих берегах торгующим людям двух государств».

В июне 1856 года указом богдыхана договор был утвержден и ратифицирован Россией. Заключая договор с Россией о границе по Амуру, китайское правительство рассчитывало на поддержку и посредничество русских в противодействии проникновению западных держав в Китай. Когда англо-французская эскадра вошла в залив Пейхо, правительство Китая обратилось к Русскому правительству с просьбой встать на защиту интересов Китая от посягательств Англии и Франции на его территорию.

В секретном предписании Государственного Совета посланнику Гуайляну 2 июня 1858 года было дано поручение довести до Русского правительства просьбу, чтобы оно «употребило усилия усовестить англичан и французов и положило предел их несправедливым требованиям» в пользу Срединного государства (Китая. — Примеч. ред.).

В 1858 году забайкальские казаки на Амур переселялись уже по жребию. «Волнение среди станичников было ужасное. Все боялись вытянуть жребий», — вспоминает современник. Был сформирован Амурский конный полк и пешая Амурская бригада. Всего в 1858 году переселилось на Амур 3696 человек обоего пола. Они организовали станицы: 13 конных и 19 пеших. К 1860 году планировалось переселить на Амур 5 тысяч человек из Забайкальского казачьего войска. Посемейные списки переселенцев утверждались губернатором Забайкальской области Михаилом Семеновичем Корсаковым, который длительное время был ближайшим помощником и единомышленником генерал-губернатора Восточной Сибири Муравьева.

26 августа 1858 года генерал-адъютант Муравьев был возведен в графы с присоединением к его фамилии «Амурского». Власть его была безгранична. Это был маленький царек Сибири. Имея твердый, вспыльчивый характер, Муравьев не терпел неисполнительности, расхлябанности, и «горе тому, кто посмел бы ослушаться его». С. Казаринов, бывший при нем почти 6 лет секретарем, вспоминает в своих мемуарах, что однажды, во время очередного сплава по Амуру, командир 3-й роты 16-го линейного батальона капитан Березовский по ошибке полковника Корсакова неправильно выполнил команду Н. Муравьева. Взбешенный небывалым случаем, Муравьев приказал баржи и плоты приставить к берегу, казаков и солдат построить в каре, вырыть яму и закопать в ней неисполнительного офицера. Однако, разобравшись с помощью Корсакова, что он не прав и судит невиновного, Муравьев извинился публично за свою «горячность», снял с себя орден Станислава 2-й степени и надел его на капитана Березовского, который за время экзекуции над ним поседел, как лунь.

Самоуправство и самодурство у Муравьева всегда граничили с щедростью и великодушием. Так, например, встретив на улице подгулявшего чиновника, который на вопрос его: «Ты кто такой?» дерзко ответил: «Секретарь иркутского земского суда, верчусь туда и сюда!» — приказал арестовать выпивоху и, «чтобы не покидал семью и не кутил бы по ночам да помнил бы царскую службу, на которой ты состоишь», — высечь его розгами. Тут же солдаты, по словам С. Казаринова, долго не медля, всыпали ему 100 розг. На следующий день через своего адъютанта Корсакова передал жене чиновника 150 рублей и напутствие, чтобы она удерживала мужа от пьянства. Узнав также, что эта семья живет бедно, приказал сына и дочь высеченного чиновника определить в гимназию на казенный счет.