Получив почту от Меншикова и письмо от Невельского, Николай Николаевич — опять-таки через Меншикова — направил на утверждение царя проект собственной инструкции командиру "Байкала", которую просил утвердить и доставить как можно скорее в Иркутск с тем, чтобы отсюда успеть переправить ее в Петропавловск к тому времени, когда там должен появиться транспорт. Одновременно, 14 сентября 1848 года, Муравьев изложил обстановку в Иркутске в письме к министру внутренних дел Л.А. Перовскому. Он сообщал, что по приезде в центр генерал-губернаторства застал там англичанина Гиля, путешествовавшего под видом туриста. Тот уже несколько месяцев находился в Иркутске, сумел втереться во все слои общества и собирал сведения об Амуре и о возможностях плавания по нему.

Муравьев постарался сделать так, чтобы спровадить любопытного англичанина подальше от Амура, рекомендовав ему побывать в Охотске и даже на Камчатке. Летом 1848 года, когда генерал-губернатор отправился в путешествие по Забайкалью, в Иркутске объявился второй "турист", тоже англичанин, некий Остин с супругой. Воспользовавшись данным ему в Петербурге разрешением и не встретив нигде возражений, Остин переправился через Байкал и через Читу прибыл в Нерчинск, где начал строить плоты, намереваясь спускаться по течению Амура.

Только на обратном пути из Кяхты, в Верхнеудинске, Узнал Муравьев об этом "путешественнике". Он немедленно отправил своего адъютанта В.В. Ваганова с приказанием ни под каким видом не допустить исполнения намерений лазутчика. Молодой поручик блестяще исполнил деликатное поручение и вернул "путешествующую" пару в Иркутск. Муравьев писал по этому поводу Перовскому, что англичанам стоит лишь только узнать о том, что "эти места никому не принадлежат" и "они непременно займут Сахалин и устье Амура: это будет делом внезапным, без всяких сношений о том с Россиею, которая однакож лишится всей Сибири, потому что Сибирью владеет тот у кого в руках левый берег и устье Амура". И дальше с горечью и обидой предупреждал министра: "Давно соображения эти занимают меня, давно собираю я сведения об этих важных для России предметах; вдруг, как снег на голову, является Остин в Нерчинск… ему стоит только спуститься по Амуру — и к будущей же весне пара английских пароходов займет Сахалин!"

Не дожидаясь ответа из Петербурга, Николай Николаевич послал Невельскому в Петропавловск свою собственную инструкцию, в которой в качестве наиболее необходимой задачи ставилось подробное описание северной части острова Сахалина (в том, что Сахалин — остров, Муравьев не сомневался) с восточной и западной его стороны; пролива, отделяющего этот остров от материка; лимана и устья Амура и залива великого князя Константина. Генерал-губернатор также извещал мореплавателя, что проект полученной им инструкции выслан на утверждение царя и что, как только документ будет утвержден и вернется в Иркутск, он будет со специальным курьером доставлен ему в Петропавловск.

Правитель Восточной Сибири имел все основания давать от своего имени такую инструкцию, так как был совершенно уверен в окончательном исходе дела в столице. Он беспокоился лишь о том, чтобы утвержденная царем инструкция успела вовремя. Беспокоился не зря: лишь 29 января 1849 года Особый комитет, назначенный по "высочайшему" распоряжению для рассмотрения амурских дел в связи с запиской Муравьева, изложил свое мнение, которое сводилось к необходимости произвести все то, что полагал необходимым восточно-сибирский губернатор. Решения комитета были утверждены царем 8 февраля. Исполнение соответствующих исследований возлагалось на экипаж военного транспорта "Байкал", командиру которого посылались соответствующие инструкции, причем предписывалось "осмотреть сколь возможно тщательнее места близ устья Амура лежащий (берег материка по северную сторону Амура и северную часть острова Сахалина) с главною целию отыскать в сих местах пункт удобной к заселению".

Первого марта все эти материалы были посланы в Иркутск, где и получены 10 апреля. Тогда же Муравьев получил и рапорт от Невельского, отправленный из Рио-де-Жанейро. Из рапорта следовало, что транспорт ранней весной сумеет прибыть в Петропавловск. Поэтому Николай Николаевич уже через день отправил М.С. Корсакова, который привез документы из Петербурга, в Петропавловск. Перед отправлением его в дальнее путешествие Муравьев, по словам Корсакова, поднял тост за "Байкал" и здоровье его командира и за успех возложенного на него предприятия.

Теперь наступило время и самому Муравьеву собираться в путешествие по Дальнему Востоку, к которому он тщательно готовился в течение целого года. Николай Николаевич полагал, что сумеет встретиться с Невельским и от него непосредственно узнать результаты исследований. Генерал-губернатору пришлось перед своим отправлением вмешаться еще раз в распоряжение правительства. Дело в том, что одновременно с решением Особого комитета о разрешении Невельскому производить свои исследования было также решено отправить экспедицию для осмотра русско-китайской границы под начальством подполковника Н.X. Ахте. Муравьев оставил офицера в Иркутске, справедливо полагая, что делать это неуместно, пока "не возбуждены будут с китайцами приличные переговоры о возвращении в наше владение левого берега этой реки". Об этом он доложил непосредственно царю.

После встречи нового, 1849 года, в который Н.Н. Муравьев и его сподвижники вступили с новыми надеждами и энергией, началась непосредственная подготовка к такому, прямо скажем, выдающемуся событию, каким было путешествие генерал-губернатора по еще далеко не освоенным просторам Дальнего Востока с заходом на Камчатку, которая даже иным коренным сибирякам представлялась "краем света". Николай Николаевич мог со спокойной душой оставить Иркутск. Замещал его по гражданской части старый его сослуживец Владимир Николаевич Зарин, недавно приехавший со своей молодой женой и молоденькими племянницами — сестрами Ельчаниновыми. Военными делами распоряжался полковник П.Н. Запольский. Получили дополнительные полномочия, каждый по своей части, такие доверенные сотрудники генерал-губернатора, как начальник Горного отделения А.Н. Таскин, горный ревизор золотых промыслов В.В. Клейменов и некоторые другие.

Первоначально в состав свиты генерал-губернатора были включены: уже упоминавшийся Б.В. Струве — заведующий канцелярией, а также хозяйственной и распорядительиой частями экспедиции, Ю.И. Штубендорф — медик и естествоиспытатель, а также препаратор М. Фурман, топограф В. Ваганов, и еще один топограф, некий Литвинов, он же и астроном. В.М. Муравьев, адъютант Николая Николаевича и его дальний родственник, неожиданно скончался. Предполагалось, что вместо него генерал-губернатора будет сопровождать М.С. Корсаков, по крайней мере на обратном пути из Петропавловска, куда он, как уже говорилось, отправился с инструкциями для Невельского.

Как ни отговаривал Николай Николаевич свою жену не искушать судьбу, Екатерина Николаевна твердо решила побывать на Камчатке. А поскольку никакой женской прислуги он брать с собой не разрешал, то в качестве ее спутницы и компаньонки в дорогу отправилась гастролировавшая в то время в Иркутске известная французская виолончелистка Элиз Христиани, единственное имущество которой составляла виолончель работы Страдивари. Любые излишества Муравьев пресекал весьма строго и решительно. Он распорядился, чтобы на 16 человек (в это количество входили казаки конвоя и погонщики лошадей) было выделено всего сорок лошадей, в то время как ранее мало-мальски знатный путешественник никак не обходился менее чем полутора сотнями. И еще характерная деталь: Муравьев выделил в распоряжение Струве точно рассчитанную на все путешествие сумму денег, вручил ему соответствующую инструкцию и маршрут и запретил обращаться к себе по каким бы то ни было вопросам, касающимся снабжения, перемены лошадей, ночевок и т. п., требуя неукоснительно при этом точного соблюдения инструкций и маршрута.