С готовыми идеями и планом изучения устьев Амура Невельской, получив назначение, обратился к тогдашнему начальнику Главного морского штаба князю А. С. Меньшикову и просил разрешения по прибытии на Камчатку отправиться на "Байкале" в Амурский лиман для описных работ.
Меньшиков, сославшись на уже состоявшееся постановление Особого комитета о передаче Амура Китаю и на тот факт, что опись его как китайской реки "повлечет нежелательную для министра иностранных дел Нессельроде неприятную переписку с китайским правительством", отказался дать такое разрешение, отметив, что кредиты Невельскому отпущены только на год и что поэтому, прибыв в Петропавловск осенью 1849 года, он не будет иметь ни времени, ни средств для осуществления своих предложений.
Одновременно, по совету Меньшикова, он обращается к незадолго перед тем назначенному генерал-губернатором Восточной Сибири Н. Н. Муравьёву, в ведении которого находились порты Тихого океана. В разговоре с Муравьёвым Невельской повторил ему свои соображения, уже изложенные Меньшикову. Муравьёв сочувственно отнесся к его планам и идеям, но помочь отказался, мотивируя тем, что все убеждены в недоступности Амура с моря, что в этом убедили и Николая I, который даже сказал: "для чего нам эта река, когда положительно уже доказано, что входить в ее устье могут только одни лодки".
Однако Невельской в словах Меньшикова о недостатке времени и средств усмотрел для себя выход: надо было выиграть время для экономии средств и, следовательно, напрячь все усилия, чтобы добиться скорейшего выхода в плавание находившегося тогда еще на стапелях в Гельсингфорсе "Байкала". Невельской добился того, что судно гораздо раньше срока было спущено на воду и 20 июля уже пришло в Кронштадт. Он вновь докладывает изумленному такой быстротой Меньшикову о готовности судна к плаванию и снова умоляет дать ему просимое разрешение для исследований и описи Амурского лимана, или, в крайнем случае, даже только юго-западного берега Охотского моря, откуда, если это потребуется, всегда можно будет Официально объяснить, что он был занесен в Амурский лиман течениями и нередкими здесь свежими ветрами. Поддержанный Муравьёвым и министром внутренних дел Л. А. Перовским, он добивается согласия Меньшикова составить проект инструкции.
В этом проекте Невельской между прочим ставил вопрос о необходимости описать юго-западный берег Охотского моря до устья Амура и самое устье, а также северо-восточный берег Сахалина до 52° северной широты. Однако Меньшиков все это вычеркнул, написав в своей инструкции весьма неопределенно, что Невельскому разрешается "...осмотреть юго-западный берег Охотского моря между теми местами, которые были определены или усмотрены прежними мореплавателями". Но ведь Крузенштерн был в лимане, Гаврилов был также в нем и заходил даже далее, поднявшись на 12