Между тем пришло решение правительства о переносе Охотского порта (от 2 декабря 1849 года). Муравьев немедленно отдал все нужные распоряжения губернатору только что образованной Камчатской области В.С. Завойко, приказав начать его уже в навигацию 1850 года, а завершить — в следующую. Докладывая обо всем этом в Петербург, генерал-губернатор особо подчеркнул бедственное положение местных жителей, страдающих от непомерных поборов и от развращающего влияния купцов, нечистых на руку: "Жители этой страны охотно обращаются в купеческих прикащиков и подторговцев для коммерческого преследования несчастных тунгусов, у которых они за бесценок выменивают дорогие звериные шкуры, развращают их и сами себя, оставляют большую часть их в нищете, в долгах купцам и в недоимке казне". И твердо, решительно дописал: "К возможному прекращению этого зла генерал-губернатором приняты все меры, которые только дозволены законом".

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

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

Дождавшись прихода "Байкала" в Аян, Невельской поспешил выйти в море. 21 июня транспорт бросил якорь в заливе Счастья. Здесь находился Орлов, который рассказал Геннадию Ивановичу о своих исследованиях и передал в его распоряжение составленную им карту побережья от Аяна до устья Амура с указанием сухопутных путей, ведущих от полуострова Константина к заливу Счастья и с указанием всех местных названий. Все это в дальнейшем очень помогло Невельскому. 29 июня он вместе с Орловым заложил на косе, отделяющей залив Счастья от Охотского моря, русское селение.

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

Вместе с письмами Невельской отправил подробное донесение Муравьеву, а затем уже на "Охотске", поскольку "Байкал" использовался для перевозки портового имущества в Петропавловск, во главе команды мастеровых 46-го флотского экипажа и казаков Якутского полка, вернулся в Петровское. Оттуда па вельботе в сопровождении шлюпки под командованием Петра Попова направился вверх по Амуру, дошел до мыса Тыр и, спускаясь обратно, задержался у устья Амгуни, поднявшись по ней на 15 верст. Возвращаясь, Геннадий Иванович основал Николаевский пост на мысе Куегда полуострова Константина, подняв здесь русский флаг. Для охраны поста он оставил Петра Попова и команду из десяти человек. 22 сентября в письме к Корсакову, с которым успел подружиться Невельской, восклицал: "1 августа при свистке боцманской дудки взлетел флаг русский на берегах Амура. Да будет он развеваться на вечные времена во славу матушки России!"

В Петровское Геннадий Иванович добирался сухим путем, через горы. Там уже строились казарма, дом начальника, офицерский флигель, баня, часовня, лавка. Орлов распоряжался умело, со знанием дела. Он знал, что он останется тут зимовать и что ему поручается начальствование обоими поселениями: тут и в Николаевском посту. А возвратившись в Аян, Невельской еще раз отправил "Охотск" под командованием П.Ф. Гаврилова в залив Счастья. Население Петровского теперь увеличилось вдвое и было обеспечено продовольствием и снаряжением на зимовку.

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