Передовые деятели России понимали, чем грозит ей «ничейное» состояние Приамурья и Приморья. Несмотря на формальный запрет, русские были частыми гостями на Амуре, где они не встречали никаких китайских «войск». Достаточно назвать плавание по Амуру до устья и далее по лиману ссыльного Гурия Васильева. В правительство поступали проекты желавших отправиться на Амур, среди которых наибольший интерес представлял проект вице-адмирала Е. В. Путятина, еще в 1843 году предложившего организовать экспедицию для исследования восточных морских границ России. В проекте ставилась задача исследовать юго-западную часть Охотского моря, избрать новое место для порта (вместо Охотска), исследовать Сахалин и попытаться установить дипломатические отношения с Японией. Но по ряду причин этот замысел не был тогда реализован.
В 1846 году адмирал Ф. П. Врангель, стоявший во главе правления компании, направил в юго-западную часть Охотского моря бриг «Константин» под командованием Александра Михайловича Гаврилова. Гаврилов входил в лиман и в устье Амура, но, скованный инструкциями министерства иностранных дел, не рискнул продолжить исследования дальше к югу. Итогом плавания А. М. Гаврилова явилась известная резолюция Николая I, в которой Амур объявлялся «бесполезной» для России рекой. И в этот момент на исторической арене появляется скромный офицер Балтийского флота капитан-лейтенант Геннадий Иванович Невельской.
Поскольку Амур являлся единственным удобным водным путем из континентальных областей России в Тихий океан, то южная часть русского Дальнего Востока во второй половине XIX века приобрела огромное значение для нашей страны. Административная деятельность генерал-губернатора Восточной Сибири Н. Н. Муравьева включала мероприятия, которые в значительной степени подготовили решение вопроса об Амуре (его поездки по Дальнему Востоку, выбор стратегических опорных точек, административные реформы, борьба с бюрократизмом, меры по развитию народного хозяйства и проч.).
В условиях растущей агрессивности тихоокеанской политики Англии и Франции, к которым скоро примкнут США, для Г. И. Невельского было ясно, что только немедленное исследование низовьев Амура даст основание для принятия правительством России правильного политического решения. Он был убежден, что Сахалин — остров, что река Амур не теряется в песках, а несет свои воды к Тихому океану. Г. И. Невельской прекрасно понимал значение Амура для России. Амур был самым коротким, самым удобным и самым дешевым путем к морю, к океану. Ему удалось добиться разрешения на исследование юго-западной части Охотского моря во время пребывания военного транспорта «Байкал» на Дальнем Востоке. Невельской был назначен командиром этого транспорта и должен был доставить в Петропавловск-Камчатский необходимые припасы для Российско-Американской компании.
21 августа 1848 года транспорт вышел из Кронштадта, 2 января 1849 года обогнул мыс Горн, а уже 12 мая «Байкал» стал на якорь в Петропавловской гавани, затратив на весь переход 8 месяцев и 23 дня — время рекордное. Сразу же по окончании разгрузки Г. И. Невельской 2 июня 1849 года вышел на транспорте к восточному берегу Сахалина и к лиману Амур.
Через 4-й Курильский пролив транспорт 7 июня вошел в Охотское море, и 12 июня начались исследования восточного побережья Сахалина, а затем и исследования в Сахалинском заливе. 27-го стали на якорь в северной части лимана, и дальнейшие исследования продолжались на шлюпках. 22 июля «достигли того места, где этот матерой берег сближается с противоположным ему сахалинским. Здесь-то, между скалистыми мысами на материке, названными мною Лазарева и Муравьева, и низменным мысом Погоби на Сахалине, вместо найденного Крузенштерном, Лаперузом, Броутоном и в 1846 году Гавриловым низменного перешейка, мы открыли пролив шириною в 4 мили и с наименьшею глубиною 5 сажен».
Это открытие послужило основным толчком к пересмотру позиций царского правительства в отношении Амура. Правда, Невельскому пришлось выдержать трудную борьбу в Петербурге, где определенная часть придворной камарильи не поверила или не захотела поверить правдивости утверждений о возможности входа в лиман и устье Амура как с севера, так и с юга, а следовательно, и об островном положении Сахалина. Но в конечном счете была образована Амурская экспедиция, начальником которой стал Г. И. Невельской, произведенный в капитаны I ранга и назначенный «состоять при генерал-губернаторе Восточной Сибири для исполнения особого возложенного высочайшего повеления и с предоставлением прав относительно пенсии, какими пользуются начальники Камчатки». Это было 8 февраля 1850 года.
Воодушевленный таким в общем-то благоприятным исходом дела, Невельской «пулей летел» обратно на Дальний Восток, туда, где в заливе Счастья, открытом во время плавания на «Байкале», был оставлен зимовать один из старожилов Дальнего Востока, Дмитрий Иванович Орлов. Невельской торопит всех и вся. Медлить нельзя. Вдруг в Петербурге раздумают — и тогда… Он намерен уже в этом году основать в устье Амура зимовье и поднять там русский флаг, чтобы в следующую навигацию доставлять сюда по Амуру продовольствие. Он надеялся, что к следующему году штат экспедиции будет утвержден, а пока приходилось довольствоваться тем, что выделил в его распоряжение Н. Н. Муравьев.
17 июня 1850 года Невельской на испытанном «Байкале», которым командовал штурманский офицер Охотской флотилии Алексей Кузьмин, поспешил в залив Счастья и, к радости своей, застал там Д. И. Орлова совершенно здоровым. У Орлова был уже готов первый вариант карты лимана Амура, руководствуясь которой можно было плавать из Амура в Охотское море по Северному фарватеру: глубины на фарватере колебались от 4 до 11 сажен.
На песчаной кошке, ограждающей залив Счастья от Охотского моря, Невельской и Орлов заложили 29 июня первое русское зимовье, названное ими Петровским. Недолго пробыл Невельской в Петровском. Он отправился в Аян, захватив с собой двух гиляков, добровольно согласившихся ехать с ним, чтобы передать русским властям просьбу всех гиляков Нижнего Амура о защите их от произвола и притеснений маньчжурских шаек. Из Аяна Невельской направился в Охотский порт, откуда вскоре с командой из 25 человек на бриге «Охотск», которым командовал Петр Федорович Гаврилов, вышел в залив Счастья.
Невельской спешил в устье Амура. На рейде Петровского бриг встретил Д. И. Орлов. Невельской немедленно — на шлюпке, в сопровождении шести матросов и двух гиляков — отправился в Амурский лиман, а по нему (Северным фарватером) вошел в устье Амура. Измеряя глубины, нащупывая фарватер, Невельской поднялся по реке на 70 миль до мыса Тыр.
На обратном пути шлюпка Невельского подошла к мысу Куегда, который был осмотрен еще на пути к Тыру по рекомендации Д. И. Орлова. 1 (13) августа 1850 года Невельской поднял здесь русский военно-морской флаг. Шесть матросов во главе с прапорщиком Петром Поповым составили первый гарнизон будущего Николаевска-на-Амуре. Невельской снабдил Попова инструкциями на случай встречи с маньчжурами и прихода в устье Амура иностранных судов: всем им было приказано заявлять о принадлежности Амура и этих мест России и, соответственно, требовать соблюдения русских законов. Сам же Геннадий Иванович на оленях отправился в Петровское. Там он оставил старшим Д. И. Орлова, а сам уехал в Аян, оттуда в Иркутск и далее в Петербург, где оказался в декабре 1850 года.
Невельского снова ждали неприятности. Ему никто не разрешал поднимать русский флаг в устье Амура и устраивать там поселение. Наряду с теми, кто восхищался его смелыми и решительными действиями, нашлись и такие государственные «деятели», которые призывали самым строгим образом наказать мореплавателя за самовольство. Был даже заготовлен приказ о разжаловании Невельского в матросы. Но заступничество Меньшикова, Муравьева и других высокопоставленных лиц привело к тому, что 12 февраля 1851 года был утвержден штат Амурской экспедиции.
В половине июня 1851 года Невельской уже в Охотске. Вместе с ним отправилась делить все тяготы кочевой жизни мужа Екатерина Ивановна Ельчанинова, на которой Геннадий Иванович женился в Иркутске. В Охотске брига «Охотск» не оказалось. В самые кратчайшие сроки Невельской сформировал основной состав экспедиции, которая 6 июля на транспорте «Байкал» и барке Российско-Американской компании «Шелихов» вышла в Аян, а оттуда, запасшись продовольствием и снаряжением, — в Петровское.