Воодушевленный таким в общем-то благоприятным исходом дела, Невельской «пулей летел» обратно на Дальний Восток, туда, где в заливе Счастья, открытом во время плавания на «Байкале», был оставлен зимовать один из старожилов Дальнего Востока, Дмитрий Иванович Орлов. Невельской торопит всех и вся. Медлить нельзя. Вдруг в Петербурге раздумают — и тогда… Он намерен уже в этом году основать в устье Амура зимовье и поднять там русский флаг, чтобы в следующую навигацию доставлять сюда по Амуру продовольствие. Он надеялся, что к следующему году штат экспедиции будет утвержден, а пока приходилось довольствоваться тем, что выделил в его распоряжение Н. Н. Муравьев.
17 июня 1850 года Невельской на испытанном «Байкале», которым командовал штурманский офицер Охотской флотилии Алексей Кузьмин, поспешил в залив Счастья и, к радости своей, застал там Д. И. Орлова совершенно здоровым. У Орлова был уже готов первый вариант карты лимана Амура, руководствуясь которой можно было плавать из Амура в Охотское море по Северному фарватеру: глубины на фарватере колебались от 4 до 11 сажен.
На песчаной кошке, ограждающей залив Счастья от Охотского моря, Невельской и Орлов заложили 29 июня первое русское зимовье, названное ими Петровским. Недолго пробыл Невельской в Петровском. Он отправился в Аян, захватив с собой двух гиляков, добровольно согласившихся ехать с ним, чтобы передать русским властям просьбу всех гиляков Нижнего Амура о защите их от произвола и притеснений маньчжурских шаек. Из Аяна Невельской направился в Охотский порт, откуда вскоре с командой из 25 человек на бриге «Охотск», которым командовал Петр Федорович Гаврилов, вышел в залив Счастья.
Невельской спешил в устье Амура. На рейде Петровского бриг встретил Д. И. Орлов. Невельской немедленно — на шлюпке, в сопровождении шести матросов и двух гиляков — отправился в Амурский лиман, а по нему (Северным фарватером) вошел в устье Амура. Измеряя глубины, нащупывая фарватер, Невельской поднялся по реке на 70 миль до мыса Тыр.
На обратном пути шлюпка Невельского подошла к мысу Куегда, который был осмотрен еще на пути к Тыру по рекомендации Д. И. Орлова. 1 (13) августа 1850 года Невельской поднял здесь русский военно-морской флаг. Шесть матросов во главе с прапорщиком Петром Поповым составили первый гарнизон будущего Николаевска-на-Амуре. Невельской снабдил Попова инструкциями на случай встречи с маньчжурами и прихода в устье Амура иностранных судов: всем им было приказано заявлять о принадлежности Амура и этих мест России и, соответственно, требовать соблюдения русских законов. Сам же Геннадий Иванович на оленях отправился в Петровское. Там он оставил старшим Д. И. Орлова, а сам уехал в Аян, оттуда в Иркутск и далее в Петербург, где оказался в декабре 1850 года.
Невельского снова ждали неприятности. Ему никто не разрешал поднимать русский флаг в устье Амура и устраивать там поселение. Наряду с теми, кто восхищался его смелыми и решительными действиями, нашлись и такие государственные «деятели», которые призывали самым строгим образом наказать мореплавателя за самовольство. Был даже заготовлен приказ о разжаловании Невельского в матросы. Но заступничество Меньшикова, Муравьева и других высокопоставленных лиц привело к тому, что 12 февраля 1851 года был утвержден штат Амурской экспедиции.
В половине июня 1851 года Невельской уже в Охотске. Вместе с ним отправилась делить все тяготы кочевой жизни мужа Екатерина Ивановна Ельчанинова, на которой Геннадий Иванович женился в Иркутске. В Охотске брига «Охотск» не оказалось. В самые кратчайшие сроки Невельской сформировал основной состав экспедиции, которая 6 июля на транспорте «Байкал» и барке Российско-Американской компании «Шелихов» вышла в Аян, а оттуда, запасшись продовольствием и снаряжением, — в Петровское.
Не доходя до Петровского, старый барк «Шелихов» затонул. Только самоотверженность экипажа и помощь подоспевшего корвета «Оливуца» под командованием капитан-лейтенанта Ивана Николаевича Сущева спасли экспедицию. Этот корвет был послан в воды Дальнего Востока для охраны русских коммуникаций, а также для защиты местных жителей от хищничества иностранных китобоев. Активное участие в спасении приняли и зимовщики Петровского под руководством Д. И. Орлова, и матросы зимовавшего там же брига «Охотск» под командованием П. Ф. Гаврилова.
