В конце января 1850 года Невельской лично представил начальнику Главного морского штаба А.С. Меншикову доклад графа Муравьёва. На его основании было принято два решения: одно о производстве Невельского в капитаны 2-го ранга, другое — о лишении его орденской награды и пенсии за то, что он провёл исследование Амурского лимана, не получив инструкции, утверждённой императором. Между тем офицеры «Байкала» получили полагавшиеся им ордена.
Российский канцлер граф К.В. Нессельроде и большинство членов кабинета министров не поверили результатам исследований Невельского в устье Амура: «противоречат Докладу графа Нессельроде и донесению барона Врангеля». В правительственных кругах Петербурга настороженно отнеслись к информации об открытии Невельского, потому что на докладе А.М. Гаврилова, почти вошедшего в лиман Амура на бриге «Константин» в 1846 году, но вынужденного повернуть назад из-за непогоды, Николай I начертал: «Весьма сожалею. Вопрос об Амуре, как о реке бесполезной, оставить».
Вместе с Корсаковым Невельской прибыл 27 марта 1850 года в Иркутск. Оттуда Корсаков направился в Охотск, а Невельской — в Аян.
По Аянскому тракту идти пришлось, используя все возможные виды транспорта: то на оленях, то верхом на лошадях, то пешком, пробираясь через заросли кедрача, то на лыжах по снегу. «Байкала» в бухте, покрытой льдом, ещё не было, но отряд Амурской экспедиции во главе с Дмитрием Орловым, не дожидаясь судна, с караваном из 40 оленей в конце февраля направился по льду Охотского моря в залив Счастья. 21 июня туда же прибыл на «Байкале» Невельской. Штурман Орлов вычертил карту берега Охотского моря от Аяна до устья Амура. Он наметил мыс Куегда как наиболее удобный для организации поселения. Невельской осмотрел мыс и выбрал место для строительства домов — на берегу залива Счастья. Он объехал близлежащие селения гиляков и, убедившись в их благожелательном отношении к русским поселенцам и в том, что китайцев там нет (а значит, Китай не претендует на эти земли), вернулся на полуостров Куегда.
29 июня 1850 года, в день святых Петра и Павла, было торжественно заложено первое русское селение в устье Амура, получившее название Петровское. Невельской на «Байкале» ушёл в Аян, а Орлов с двенадцатью матросами остался обживать новый населённый пункт России.
В Петропавловске Невельской рассказал о своих действиях камчатскому генерал-губернатору В.С. Завойко и архиепископу Иннокентию, отправил письмо Корсакову, где изложил то же самое, закончив словами: «Если же генеральское решение не дойдёт до меня... сами распорядимся — смелость, быстрота и движение!»
Как только представилась возможность, Невельской снова отправился в залив Счастья на бриге «Охотск» под командой Петра Гаврилова.
К первым тринадцати поселенцам Петровского присоединились казаки Якутского полка и мастеровые флотского экипажа. Невельской совершил плавание по Амуру и Амгуни, а вернувшись, 6 августа поднял русский военно-морской флаг над постом Николаевским, основанным им на полуострове Куегда. Второй населённый пункт в устье Амура учреждён без санкции центральной власти и царя. Это было неслыханным самоуправством. Но Невельской был уверен, что его действия будут оправданы: он знал известное изречение царя: «Где раз поднят русский флаг, он уже спускаться не должен».
Прошли годы, и на месте самоуправно основанного поста возник город и порт Николаевск-на-Амуре.
Оставив Орлова зимовать в Петровском, Невельской выехал из Аяна в Иркутск, чтобы заручиться поддержкой Муравьёва, а потом — в Петербург, куда вскоре приехал и сибирский генерал-губернатор. Он подал на имя государя записку, в которой доказывал: на Амуре надо всё оставить так, как сделал Невельской. Сначала это послание прочитали члены Особого комитета графа Нессельроде и были возмущены самовольными действиями дерзкого капитана 2-го ранга. Военный министр А.И. Чернышев потребовал разжаловать его в матросы. Невельского защитили министр внутренних дел А.С. Меншиков и А.А. Перовский (отец будущего народовольца Софьи Перовской), но главную роль сыграла записка Муравьёва. Император распорядился созвать новое заседание Особого комитета. 19 января была обсуждена записка Муравьёва и в комитете произошёл раскол. Группа чиновников во главе с Нессельроде и Чернышевым требовала отмены всех «установлений» дерзкого Невельского. В конце концов было принято решение: оставить Николаевский пост «в виде торговой точки Российско-Американской компании, но никаких дальнейших распространений в этой стране не предпринимать и отнюдь никаких мест не занимать» и направить в Петровское и Николаевское 60 матросов и казаков, «при двух офицерах и докторе». Самый же главный пункт гласил: «Экспедицию эту назвать Амурскою и начальником её во всех отношениях назначить капитана 1-го ранга Невельского».
Это была победа над бюрократией и нерешительностью властей. В осуществлении давней мечты об открытии судоходного устья Амура нашёл Невельской своё счастье. И не случайно так назвал он залив. Совпало с ощущением исполненного долга и личное счастье. В апреле 1851 года состоялась его свадьба, и он поехал на Амур с юной женой Екатериной Ельчаниновой, дочерью иркутского гражданского губернатора. Муравьёв из Петербурга писал: «...продолжайте начатое, и всё будет хорошо». Он сообщил также, что в экспедицию назначен молодой офицер, лейтенант Николай Бошняк, с отцом которого Невельской был хорошо знаком.
Амурская экспедиция добралась до Аяна на «Байкале», дальше пришлось идти на барке Российско-Американской компании «Шелихов». На «Байкале», которым командовал А.И. Воронин, был размещён экспедиционный груз. Народу собралось немало — 60 пассажиров, многие ехали на поселение с жёнами и детьми.
До залива Счастье два судна дошли за пять дней, но здесь, у входа в счастливый залив, с «Шелиховым» случилась беда: в густом тумане он налетел на скалу и получил пробоину в днище. Вода быстро заполнила всё помещения судна, и барк начал тонуть. На верхней палубе столпились все пассажиры. С помощью команды «Байкала» и кстати подошедшего корвета «Оловус» под умелым руководством бывалых капитанов с тонущего барка сняли всех людей и доставили их на берег...
А.П. Чехов написал о Невельском в своей книге «Остров Сахалин»: «Это был энергичный, горячего темперамента человек, образованный, самоотверженный, гуманный, до мозга костей проникнутый идеей и преданный ей фанатически, чистый нравственно».
Вполне справедливая оценка...
Проникнув в устье Амура и открыв возможность судоходства, Невельской взял на себя задачу исследования и освоения огромного региона, создания в нём первых поселений, чтобы никто не усомнился в том, что эта земля принадлежит России. Он возглавил Амурскую экспедицию, в которую вошли морские офицеры — бесстрашные, самоотверженные люди, энтузиасты. Невельской организовал несколько исследовательских походов по Приамурью и Сахалину. В состав Амурской экспедиции, кроме Николая Бошняка, вошли Николай Чихачёв, Дмитрий Орлов, Григорий Разградский. Подбор помощников был очень удачный, они способны были действовать самостоятельно. Сподвижники Невельского, следуя его инструкциям, открывали новые заливы, реки, озёра, острова, избирали места для строительства поселений, устанавливали дружеские контакты с населявшими эти земли гиляками (нивхами), которые доброжелательно относились к русским: участвовали в их походах, стойко перенося трудности.
В одном из отчётов морскому начальству Невельской писал: «Гиляки в исследованиях... усердно помогали, показывали фарватеры, хранили товары и не только не оказывали какое-либо неудовольствие, чтобы у них строились, а, напротив, радовались и толпами приходили с просьбою защищать их от своеволия команд китобойных судов, берега Охотского моря часто посещающих».
Основывая каждое новое поселение, Невельской вручал кому-либо из нивхов декларацию на русском, английском и французском языках о том, что здесь находятся владения России. Сам он постоянно перемещался между Охотском, Аяном и основанными постами Петровским и Николаевским, разделёнными горным хребтом.
