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