Путешествие началось 15 мая 1849 года, едва только сошел лед на Лене. На Качугской пристани его участников ожидали три "повозка". [7]На первом шел Муравьев с супругой и мадемуазель Христиани. Здесь была столовая, в которой дважды в день — к завтраку и обеду — собиралась вся свита. Тут же стоял стол, за которым генерал работал и принимал доклады чиновников. На втором повозке разместились чиновники, топограф и лаборант-препаратор, на третьем — кухня с прислугой. Кроме 16 участников экспедиции, на повозках размещалось 30 нижних чинов, отправлявшихся в Охотск. Ими распоряжался В.В. Ваганов, и они составляли главную рабочую силу.
На остановках местные жители привозили рыбу, приходили приветствовать губернатора, вручать свои жалобы. Муравьев по пути ревизовал волостные правления, отложив ревизии Киренска, Олекминска и Якутска на обратный путь. Причем ревизии, как правило, не задерживали продвижение каравана, поскольку Николай Николаевич выезжал вперед на небольшой лодке, а затем таким же порядком догонял медленно плывущие повозки.
В Якутске задержались на трое суток. И то только затем, чтобы подготовиться к вьючному путешествию по Охотскому тракту. Путь лежал к Амгинской слободе, а оттуда по тропам и узким горным дорогам через горный перевал — к Охотску. И уже после первого двадцатипятиверстного перехода Екатерина Николаевна почувствовала себя настолько разбитой и уставшей, что отказывалась без отдыха ехать дальше. Последовало объяснение на французском языке, после которого Муравьев возвратился к каравану и распорядился отправить жену в сопровождении камердинера обратно в Якутск, где она вольна возвратиться в Иркутск или же ожидать его возвращения с Камчатки.
И едва была дана команда трогаться, как показалась заплаканная молодая генеральша и стала просить, чтобы ей помогли взобраться на лошадь. Муравьев рассчитал правильно, по-военному: уступи он один раз, такое продолжалось, быть может, каждый день, и все равно супруга не привыкла бы к тяготам путешествия; а тут, переборов себя раз-два, она в дальнейшем уже была весела и сама смеялась над своей слабостью. Испытать же пришлось многое — не только бездорожье, но еще разливы рек, проливные дожди и беспощадные нападения гнуса — мелких комаров, от которых не было никакого спасения, несмотря на различные приспособления и ухищрения.
25 июня генерал-губернатор прибыл в Охотский порт, где был встречен начальником порта И.В. Воилярлярским, командиром транспорта "Иртыш" капитаном второго ранга В.К. Поплонским, тем самым, который два года назад открыл залив Константина, другими офицерами и чиновниками. Порт произвел на Муравьева такое отвратительное впечатление, что он не стал тут долго задерживаться, разрешив своим спутникам лишь немного отдохнуть. А затем молебен, переселение на борт "Иртыша" и… неудачный выход в море. Охотск подтверждал свою дурную репутацию: "Иртыш" выбросило на бар. [8]Только 7 июля удалось, наконец, покинуть порт.
Переход на Камчатку также не был легким. Тихоход-транспорт еле справлялся с встречным ветром. Особенно трудным оказался переход по проливу между островами Онекотан и Парамушир, когда по выходе в Тихий океан едва избежали крушения у мыса Васильева. Тут же сумели оказать помощь французскому китобою, с которым вместе и добрались до Авачинской губы. "Я много видел портов в России и в Европе, — писал 7 августа Муравьев Перовскому, — но ничего подобного Авачинской губе не встречал. Англии стоит сделать умышленно двухнедельный разрыв с Россиею, чтобы завладеть ею и потом заключить мир, но уж Авачинской губы она нам не отдаст и если б даже заплатила нам миллион фунтов за нее при заключении мира, то выручит его в самое короткое время от китобойства в Охотском и Беринговом морях. Англия, разумеется, никого не пустит в эти моря беспошлинно". Оснований для беспокойства было достаточно: и во время плавания на Камчатку, и особенно на обратном пути, вблизи Сахалина, Муравьев и его спутники видели часто иностранных китобоев.
В Петропаловске Николай Николаевич узнал о невероятно смелом, почти доходящем до дерзости, поступке Г.И. Невельского. Начальник Камчатки капитан первого I ранга Р.Г. Машин сообщил, что Геннадий Иванович с "Байкалом" прибыл сюда 12 мая, поспешно разгрузил транспорт, некоторое время ожидал обещанной инструкции из Петербурга и, наконец, решил выйти в море лишь с теми заданиями, которые дал ему от себя Муравьев. Иными словами, вышел в плавание, не имея утвержденных царем полномочий. Николаю Николаевичу было известно, что царь утвердил их, но Невельской этого не знал. Генерал-губернатор прекрасно понимал, чем такое может грозить командиру "Байкала". Беспокойство его возросло еще и потому, что вышедший ранее из Охотского порта на боте "Кадьяк" М.С. Корсаков вместе с командиром бота Н.И. Шарыповым в Петропавловске не появлялся. Можно было предположить, что Корсаков ищет Невельского там, где может оказаться транспорт "Байкал": в Сахалинском заливе или возле Шантарских островов. Муравьеву ничего не оставалось иного, как, решив все вопросы в Петропавловске, самому отправиться на поиски неуловимого Невельского.
Перед отплытием Николай Николаевич тщательно осмотрел берега Петропавловской гавани и сам наметил наиболее удобные места для установки батарей. Здесь же решился и вопрос о кандидатуре будущего камчатского губернатора. Он был решен в беседе Муравьева с архиепископом Камчатским и Алеутским Иннокентием Вениаминовым. Вдвоем они пришли к выводу, что наилучшим кандидатом на этот пост будет Василий Степанович Завойко, а не Иван Васильевич Вонлярлярский, который был вначале у Муравьева на приеме. С 25 июля по 2 августа пробыл Муравьев в Петропавловске и окончательно решил вопрос о перенесении российского тихоокеанского порта. А Екатерине Николаевне Камчатка настолько понравилась, что она высказала желание поселиться тут навсегда. "По крайней мере, — добавила она, — после отставки мужа".
Перед уходом в плавание к берегам Сахалина Муравьев послал Л.А. Перовскому письмо-представление, в котором наметил программу преобразований здешнего края. Он предлагал упразднить Охотский порт и перевести его в Петропавловск. Одновременно следовало упразднить также и Охотское приморское управление, а входящие в него округа подчинить: Охотский — Якутскому областному начальнику, а Гижигинский — Камчатскому военному губернатору. Камчатскую область с присоединенным к ней Гижигинским округом возвести в ранг губернии и назначить военным губернатором моряка, причем именно В.С. Завойко, с присвоением ему чина контр-адмирала. Муравьев считал необходимым построить в Аяне порт Российско-Американской компании. Намечал он также переселить на Камчатку и в Охотский край до трех тысяч семейств русских земледельцев, перечислял необходимые меры для укрепления Авачииской губы и охраны прилегающих морей от иностранных китобоев.
Возвращаясь на "Иртыше" из Петропавловска в Аян (а он решил возвращаться не через Охотск, а через Аян, дабы осмотреть и этот порт), генерал-губернатор почти наверняка рассчитывал встретить в море Корсакова па "Кадьяке", а может быть, и самого Невельского на "Байкале". Но по выходе из Авачииской губы мореплаватели попали в штиль, который задержал продвижение почти на десять суток. И при этом стояла жестокая мертвая зыбь, от которой досталось всем, а более всего, конечно, женщинам. Не помогло даже искусство опытного капитана, каковым, несомненно, был В.К. Поплонский, — транспорт качало неимоверно. Уйти от этой качки помог бы только ветер, а его не было.
Затем долго и безуспешно искали встречи с русскими кораблями, но в большом количестве встречали лишь иностранных китобоев. "Кадьяка" и "Байкала" нигде не было. Сначала пошли к Сахалину. "Иртыш" лег в дрейф между траверсами мысов Елизаветы и Марии. 22 августа на берег отправились Ваганов, Струве и Штубендорф. Ваганов произвел глазомерную съемку местности, Штубендорф занимался сбором трав, растений, камней, а Струве выменивал у местных жителей гиляков (нивхов) свежую рыбу и расспрашивал о "Байкале", но так и не узнал ничего. После возвращения посланцев на борт "Иртыша" Муравьев приказал идти к Шантарским островам. Там тоже высаживались на берег. Но и на Шантарах Невельского не оказалось, и никто из местных жителей ничего о нем не слыхал.