К 12 мая весь караван выстроился на фарватере Шилки. Возглавлял его пароход "Аргунь" под командованием А.С. Сгибнева. Флотилия растянулась на две версты. 14 мая после необычного артиллерийского салюта из старинной пушки, стрелявшей еще при обороне Албазина, флотилия отправилась вниз по реке. Зрелище было великолепным: впереди шел пароход под генеральским флагом, затем наперегонки неслись три офицерские лодки, за ними вереницей двигались плоты, баржи и плашкоуты. Но поскольку их команды состояли из солдат и казаков, не имевших опыта в управлении судами, они довольно часто садились на мель или прибивались течением к берегу.
Через четверо суток, 18 мая, флотилия вышла в Амур. Под звуки гимна Муравьев зачерпнул стакан амурской воды и поздравил всех с началом плавания по великой реке. Громовое "ура!" огласило живописные, но пустынные берега. Лишь на Усть-Стрелочном посту русские солдаты ликовали вместе с плывущими. При прохождении древнего Албазина флотилия пристала к берегу. Был объявлен привал на сутки. Первым сошел на берег генерал- губернатор. Все устремились к тому месту, где когда-то стоял форпост Отечества, героический город.
"Я съехал с парохода на берег, — вспоминал впоследствии А. С. Сгибнев, — и обошел весь вал, облегавший крепость с трех сторон и сохранившийся до настоящего времени. Вал этот обнесен рвом и имеет форму правильного четырехугольника, каждая сторона которого длиною до 60-ти сажен. Внутри крепости и за ней видны ямы — следы бывших здесь жилых зданий, около которых вырыт колодец. Волнистая местность вблизи вала служит явным признаком бывших здесь огородных гряд, а далее, на версту в квадрате, очищенное место от камней, где, по всей вероятности, были пашни албазинцев. В версте от Албазина у небольшой речки была устроена албазинцами мельница, от которой жернова лежали на берегу до нашего прибытия. Общество наше после завтрака на валу разбрелось во все стороны. Каждый старался отыскать себе что-нибудь на память. Рыли ямы и вал кольями. В ямах находили черепки глиняной посуды и железные наконечники от китайских стрел, а в валу ядра и пули. Эти остатки боевой славы албазинцев невольно наводили на мысль о их прошлом, и я ходил около вала, возобновляя в памяти историю Албазина, пока не подан был сигнал к отплытию экспедиции". Корсаков в своих записках рассказывает, что испытал те же чувства и сообщает, что "взял для памяти вырытый из земли кирпич и горсть почерневшей, уцелевшей от времени пшеницы".
Дальнейшее плавание проходило успешно. Плыли мимо мест, навечно связанных с памятью о русских первопроходцах. Проходя мимо Кумарской скалы, вспомнили, что в 1652 году здесь был поставлен Кумарский острог, выжженный затем маньчжурами. Пройдя "щеки", флотилия вскоре подошла к устью Зеи, откуда Муравьев направил вперед, к Айгуну, нарочных с извещением о прибытии русской флотилии. И когда пароход "Аргунь" в сопровождении четырех лодок встал у города, то его уже встречал амбань (губернатор). Сперва сановник пытался воспрепятствовать дальнейшему плаванию, ссылаясь на то, что не получал от своего правительства никаких указаний. Но это делалось скорее для виду. Чувствовалось, что амбаню хотелось, чтобы огромная, как ему казалось, русская флотилия поскорее покинула пределы его города.
Ветеран-казак Р.К. Богданов, много служивший с Муравьевым, оставил любопытные воспоминания о том, как проводил свое время в походе деятельный генерал-губернатор: "Каждый день генерал вставал чуть заря, никогда никто его не будил, почти до солнечного восхода пил чай, больше на палубе, носил серую армейскую шинель, подбирая подол кверху, на пуговки, изображая из солдатской шинели сюртук. С орденом на шее или в петлице, любил орден за выслугу 25 лет. По выходе утром на палубу здоровался с каждым, спрашивал, была ли вчера каша. Утрами и вечерами, наипаче в дождливое время, ходил осматривать ближние ночлеги, как останавливаются и отчаливают сплавные суда отряда или осматривал луговые места…"
Обычно Николай Николаевич брал с собой кого-либо из сопровождавших его офицеров, чаще других Моллера, Хилковского и Венюкова. Если они простуживались после таких прогулок под дождем, а чаще всего это случалось с Моллером, Муравьев ехидно посмеивался над ними. Дальнейший распорядок Р.К. Богданов описывает так: "До 12 часов дня почти все время находился на палубе; после закуски отдыхал, не более часа, а затем опять выходил на палубу, здоровался и разговаривал с солдатами на баркасе или с теми, кого обгоняли из отряда… Обедал около 4 часов, а после обеда опять выходил на палубу". Как свидетельствует ветеран, Муравьев много плавал на лодке во время стоянок, ел солдатские щи и кашу с ржаными сухарями. Ложился спать позже всех, любил сидеть один в темноте на палубе. Примечателен характер взаимоотношений генерала с подчиненными, о котором Богданов рассказывает в таких словах: "Солдат любил, как братьев, а они его тоже любили и уважали, а с офицерами был грубоват, требовал благоразумия и энергии, наипаче с своих свитских. Терпеть не мог "точно так" и "не могу знать".