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