29 июня 1850 года, в день святых Петра и Павла, было торжественно заложено первое русское селение в устье Амура, получившее название Петровское. Невельской на «Байкале» ушёл в Аян, а Орлов с двенадцатью матросами остался обживать новый населённый пункт России.

В Петропавловске Невельской рассказал о своих действиях камчатскому генерал-губернатору В.С. Завойко и архиепископу Иннокентию, отправил письмо Корсакову, где изложил то же самое, закончив словами: «Если же генеральское решение не дойдёт до меня... сами распорядимся — смелость, быстрота и движение!»

Как только представилась возможность, Невельской снова отправился в залив Счастья на бриге «Охотск» под командой Петра Гаврилова.

К первым тринадцати поселенцам Петровского присоединились казаки Якутского полка и мастеровые флотского экипажа. Невельской совершил плавание по Амуру и Амгуни, а вернувшись, 6 августа поднял русский военно-морской флаг над постом Николаевским, основанным им на полуострове Куегда. Второй населённый пункт в устье Амура учреждён без санкции центральной власти и царя. Это было неслыханным самоуправством. Но Невельской был уверен, что его действия будут оправданы: он знал известное изречение царя: «Где раз поднят русский флаг, он уже спускаться не должен».

Прошли годы, и на месте самоуправно основанного поста возник город и порт Николаевск-на-Амуре.

Оставив Орлова зимовать в Петровском, Невельской выехал из Аяна в Иркутск, чтобы заручиться поддержкой Муравьёва, а потом — в Петербург, куда вскоре приехал и сибирский генерал-губернатор. Он подал на имя государя записку, в которой доказывал: на Амуре надо всё оставить так, как сделал Невельской. Сначала это послание прочитали члены Особого комитета графа Нессельроде и были возмущены самовольными действиями дерзкого капитана 2-го ранга. Военный министр А.И. Чернышев потребовал разжаловать его в матросы. Невельского защитили министр внутренних дел А.С. Меншиков и А.А. Перовский (отец будущего народовольца Софьи Перовской), но главную роль сыграла записка Муравьёва. Император распорядился созвать новое заседание Особого комитета. 19 января была обсуждена записка Муравьёва и в комитете произошёл раскол. Группа чиновников во главе с Нессельроде и Чернышевым требовала отмены всех «установлений» дерзкого Невельского. В конце концов было принято решение: оставить Николаевский пост «в виде торговой точки Российско-Американской компании, но никаких дальнейших распространений в этой стране не предпринимать и отнюдь никаких мест не занимать» и направить в Петровское и Николаевское 60 матросов и казаков, «при двух офицерах и докторе». Самый же главный пункт гласил: «Экспедицию эту назвать Амурскою и начальником её во всех отношениях назначить капитана 1-го ранга Невельского».

Это была победа над бюрократией и нерешительностью властей. В осуществлении давней мечты об открытии судоходного устья Амура нашёл Невельской своё счастье. И не случайно так назвал он залив. Совпало с ощущением исполненного долга и личное счастье. В апреле 1851 года состоялась его свадьба, и он поехал на Амур с юной женой Екатериной Ельчаниновой, дочерью иркутского гражданского губернатора. Муравьёв из Петербурга писал: «...продолжайте начатое, и всё будет хорошо». Он сообщил также, что в экспедицию назначен молодой офицер, лейтенант Николай Бошняк, с отцом которого Невельской был хорошо знаком.

Амурская экспедиция добралась до Аяна на «Байкале», дальше пришлось идти на барке Российско-Американской компании «Шелихов». На «Байкале», которым командовал А.И. Воронин, был размещён экспедиционный груз. Народу собралось немало — 60 пассажиров, многие ехали на поселение с жёнами и детьми.

До залива Счастье два судна дошли за пять дней, но здесь, у входа в счастливый залив, с «Шелиховым» случилась беда: в густом тумане он налетел на скалу и получил пробоину в днище.