С готовыми идеями и планом изучения устьев Амура Невельской, получив назначение, обратился к тогдашнему начальнику Главного морского штаба князю А. С. Меньшикову и просил разрешения по прибытии на Камчатку отправиться на "Байкале" в Амурский лиман для описных работ.
Меньшиков, сославшись на уже состоявшееся постановление Особого комитета о передаче Амура Китаю и на тот факт, что опись его как китайской реки "повлечет нежелательную для министра иностранных дел Нессельроде неприятную переписку с китайским правительством", отказался дать такое разрешение, отметив, что кредиты Невельскому отпущены только на год и что поэтому, прибыв в Петропавловск осенью 1849 года, он не будет иметь ни времени, ни средств для осуществления своих предложений.
Одновременно, по совету Меньшикова, он обращается к незадолго перед тем назначенному генерал-губернатором Восточной Сибири Н. Н. Муравьёву, в ведении которого находились порты Тихого океана. В разговоре с Муравьёвым Невельской повторил ему свои соображения, уже изложенные Меньшикову. Муравьёв сочувственно отнесся к его планам и идеям, но помочь отказался, мотивируя тем, что все убеждены в недоступности Амура с моря, что в этом убедили и Николая I, который даже сказал: "для чего нам эта река, когда положительно уже доказано, что входить в ее устье могут только одни лодки".
Однако Невельской в словах Меньшикова о недостатке времени и средств усмотрел для себя выход: надо было выиграть время для экономии средств и, следовательно, напрячь все усилия, чтобы добиться скорейшего выхода в плавание находившегося тогда еще на стапелях в Гельсингфорсе "Байкала". Невельской добился того, что судно гораздо раньше срока было спущено на воду и 20 июля уже пришло в Кронштадт. Он вновь докладывает изумленному такой быстротой Меньшикову о готовности судна к плаванию и снова умоляет дать ему просимое разрешение для исследований и описи Амурского лимана, или, в крайнем случае, даже только юго-западного берега Охотского моря, откуда, если это потребуется, всегда можно будет Официально объяснить, что он был занесен в Амурский лиман течениями и нередкими здесь свежими ветрами. Поддержанный Муравьёвым и министром внутренних дел Л. А. Перовским, он добивается согласия Меньшикова составить проект инструкции.
В этом проекте Невельской между прочим ставил вопрос о необходимости описать юго-западный берег Охотского моря до устья Амура и самое устье, а также северо-восточный берег Сахалина до 52° северной широты. Однако Меньшиков все это вычеркнул, написав в своей инструкции весьма неопределенно, что Невельскому разрешается "...осмотреть юго-западный берег Охотского моря между теми местами, которые были определены или усмотрены прежними мореплавателями". Но ведь Крузенштерн был в лимане, Гаврилов был также в нем и заходил даже далее, поднявшись на 12 км вверх по самому Амуру. Где можно было провести грань между тем, что разрешалось и чего нельзя делать, чтобы не навлечь на себя наказания, которым Меньшиков пригрозил Невельскому в случае ослушания или неблагополучия судном?
При этих условиях Невельской, желая заручиться поддержкой Н. Н. Муравьёва, пишет тому в Иркутск письмо, сопровождает его проектом инструкции, которую просит просмотреть, и, поддержав ее, переслать обратно в Петербург для утверждения. В одном из пунктов этой инструкции значилось, что Невельской должен был "описать юго-восточный (фактически, конечно, юго-западный. -- Л. К.) берег Охотского моря и берега Татарского залива". Понимая, что без утверждения инструкции, в которой бы прямо говорилось о необходимости описи Амурского лимана и Амура, он в случае неудачи рискует очень многим, Невельской, не в пример Гаврилову, который, несмотря на огромную важность поставленной перед ним задачи, нашел мотивировки для оправдания ее невыполнения, писал Муравьеву, что он "великолепно понимает значение познания этой страны для России и употребит все свои силы и способности, чтобы представить добросовестную картину мест, доселе закрытых мраком".
21 августа 1848 года "Байкал" вышел из Кронштадта, 15 ноября бросил якорь в Рио-де-Жанейро, 2 января 1849 года пересек меридиан мыса Горн на Огненной Земле, зашел в Вальпарайзо и Гонолулу и 12 мая 1849 года, на 2,5 -- 3 месяца раньше срока, прибыл в Петропавловск. Таким образом, в распоряжении Невельского оказывалось свободным для исследований все лето. Но... вместо утвержденной инструкции, которую он надеялся получить в Петропавловске, ему был вручён лишь пакет с письмами Муравьёва и копией инструкции, посланной им для утверждения в С.-Петербург, но утвержденной инструкции не было. Пока шла разгрузка корабля, положение еще было терпимо, но когда она кончилась, а инструкция все еще не прибыла, Невельской принял решение действовать на собственный страх и риск. Он созвал к себе в каюту помощников и ознакомил их со своими планами. "На нашу долю, -- сказал он, -- выпала... важная миссия, и я надеюсь, что каждый из нас исполнит свой долг перед отечеством... Правда об устьях Амура будет раскрыта". В сознании своего долга он торопит всех и 30 мая, как только были получены с Алеутских островов байдарки, нужные ему для исследований в Амурском лимане, "Байкал" отдал концы и направился на юг.
12 июня Невельской был у восточных берегов Сахалина и, после пятнадцатидневного плавания, 27 июня подошёл к мысу Головачёва на Сахалине, с северо-востока, ограждающего Амурский лиман, и приступил к его описи с корабля и шлюпок.
Лабиринт мелей, быстро сменявшиеся направления течений и встречные южные ветры, с которыми маленькому суденышку трудно было бороться, особенно при незнакомстве с фарватером, заставили Невельского отказаться от мысли исследовать всю огромную площадь Амурского лимана и ограничиться рекогносцировкой. Считая, что наиболее глубокие места, лишенные мелей, должны находиться под защитой берегов, Невельской послал к западному берегу шлюпку, за которой последовал сам на "Байкале" параллельно мели, действительно преграждавшей путь дальше на юг в лиман. Под материковым берегом, против, мыса Ромберга, "Байкал" встретил, наконец, глубины, которые позволили ему обогнуть отмель и при глубине 8--9 м войти в лиман, где корабль и был поставлен на якорь. Отсюда Невельским были отправлены две шлюпки для изучения сахалинского берега и одна в устье Амура под командованием П. В. Козакевича, который, дойдя до мыса Тебах, обнаружил к западу от него бухту, из которой шло сильное течение. Это было устье Амура.
10 июля Невельской на трех шлюпках сам отправился в плавание, создавшее ему славу и признательность поколений. 11 июля он обогнул мыс Тебах и вступил в Амур. Дойдя до мыса Куегда на левом берегу Амура, он повернул к правому берегу и, следуя под ним вниз по течению снова вышел в лиман. Придерживаясь материкового берега, Невельской 22 июля (3 августа) достиг наконец самого узкого места в Татарском проливе.