На станции Сергиевской под Тулой во время личного разговора Николай Павлович объявил, что назначает Муравьева генерал-губернатором Восточной Сибири с сугубо тайной задачей. Построить Тихоокеанскую береговую укрепленную линию, по опыту Черноморской, и наладить охрану границы с Китаем. Муравьев прибыл в столицу. Четыре месяца изучал материалы по Сибири, общался с людьми, знающими местные проблемы. На него вышел и Невельской со своими предложениями. Муравьев горячо поддержал их. Подключили начальника Главного морского штаба Меншикова, великого князя Константина, и Невельского назначили капитаном транспортного судна «Байкал» – оно должно было из Петербурга доставить грузы в Петропавловск-Камчатский. Новый генерал-губернатор и Невельской составили прошение государю разрешить экспедицию к устью Амура, проект инструкций на высочайшее утверждение.
После этого Муравьев отправился в свои «владения». Трудностей он не чурался. Сам проделал путь на океанское побережье – хотя для этого надо было из Иркутска добираться до Якутска, потом путешествовать по притокам Лены, перевалить хребет Джугджур. В общем, на себе проверил, что прочной связи эта дорога не обеспечивает. Осмотрев Охотск и Аян, Муравьев на транспорте «Иртыш» в 1849 г. добрался до Петропавловска, оценив уникальные условия Авачинской губы. Доложил министру внутренних дел Перовскому: «Я много видел портов в России и Европе, но ничего подобного Авачинской губе не встречал». Но генерал-губернатор указывал, что такую великолепную гавань необходимо серьезно укрепить, иначе ее просто отберут у русских. Встревоженно писал, что сам застал здесь 2 британских военных корабля, разведывающих русские берега под предлогом поисков полярной экспедиции Франклина. Обороной Петропавловска Муравьев занялся безотлагательно. Комендантом назначил энергичного и толкового генерала Завойко, определил места для артиллерийских батарей.
Ну а транспорт Невельского «Байкал» в августе 1848 г. отчалил из Кронштадта, пересек Атлантический и Тихий океаны и в мае 1849 г. тоже прибыл в Петропавловск. Надеялись, что к этому времени подоспеет царское разрешение на Амурскую экспедицию, но его не было. Судя по всему, прошение так и застряло в Особом Комитете, и государю его вообще не доложили. Но Невельской начал действовать по инструкции Муравьева, так и не утвержденной императором. Разгрузив судно, взял курс на Сахалин. Останавливался у берега, расспрашивал местных жителей, и уже в июне нашел Амурский лиман, а затем и устье реки. Встал на якорь, на лодках прошел по Амуру несколько десятков километров. Убедился, что река судоходна. Потом обследовал берега на юг от нее и совершил еще одно открытие – обнаружил узкий, шириной 7 км, пролив между материком и Сахалином, который сейчас называется проливом Невельского. На «Байкале» прошелся и по Охотскому морю, исправляя многочисленные неточности на картах.
1 сентября он причалил в Аяне, где находился и Муравьев, доложив о блестящих результатах. Генерал-губернатор сразу послал донесение в столицу, отправив туда и самого Невельского. Приложил свой план занять устье Амура, а в перспективе и всю реку. Еще находясь в Петербурге, он слышал от Нессельроде и других сановников выводы, что охранять границу с Китаем, а тем более противостоять каким-либо враждебным действиям, Россия все равно не способна, у нее не хватит сил и средств, чтобы держать здесь большие постоянные контингенты. Но и в этом вопросе он нашел решение из своего кавказского опыта. Предложил царю создать Амурское казачье войско – одновременно для заселения и охраны границы.
Однако в Особом Комитете и министерстве иностранных дел известие об открытиях вызвало бурю возмущения. Плавание к Амуру называли авантюрой, вредной для России «выходкой». Царь посмотрел на дело иначе. Невельского он повысил в чине сразу на несколько ступеней, в капитаны 2-го ранга. Но проекты Муравьева Нессельроде совсем «заглушил». Пугал, что Китай начнет войну, что выступит Англия – а шел 1849 г., отношения с ней и без того испортились Венгерским походом. В итоге Невельского отправили обратно в распоряжение Муравьева. Но инструкции напрочь урезали. Генерал-губернатору предписывалось основать новую базу для торговли с местными племенами на юго-восточном берегу Охотского моря, «но отнюдь не в Амурском лимане, а тем более не на реке Амуре». Это требование подчеркивалось дополнительно, «ни под каким видом и предлогом не касаться лимана и реки Амур». Как раз для строительства торговой базы предназначался Невельской, ему выделяли 25 матросов и казаков.