Тем временем Невельской, при содействии вице-председателя географического общества, вице-адмирала Ф.П. Литке добился приема у начальника Главного морского штаба (как называлась тогда должность руководителя морского ведомства), генерал-адъютанта светлейшего князя А.С. Меншикова. Князь, уже посвященный в суть дела Муравьёвым и министром внутренних дел графом Л.А. Перовским, тем не менее, отнесся к ходатайству подчинённого скептически. На него, видимо, повлияли уверения Нессельроде, что по Нерчинскому трактату китайцам принадлежат оба берега Амура. И если ускорению постройки "Байкала" начальник Главного морского штаба вполне сочувствовал, подписав соответствующее обращение к владельцам гельсингфорсской фирмы "Боргстрем и К°", то выходить за рамки первоначальной задачи транспорта - доставки продовольствия в Петропавловск - не разрешил. Невельскому пришлось отправить Муравьёву письмо с просьбой о поддержке. Она не заставила себя ждать, однако ничего не изменила. Нессельроде, ссылаясь на высочайшее повеление покончить с амурским вопросом, удержал опытного царедворца Меншикова от самостоятельных действий.
Между тем, об Амуре заговорили в правящих кругах, и канцлеру пришлось выступить с двумя официальными записками, доказывавшими, что Китай владеет левым берегом реки. Нессельроде пугал правительство возможностью дипломатических осложнений из-за Амура и соглашался только на крейсерство у берегов Сахалина одного военного корабля, а лучше судна Российско-американской компании, дабы эта мера казалась частной инициативой. Под воздействием таких аргументов Ментиков отказал командиру "Байкала" и после того, как летом 1848 года транспорт со значительным опережением сроков был вооружён и переведён в Кронштадт. Лишь перед самым отплытием Невельского на Дальний Восток благодаря влиянию братьев Перовских князь уступил. Однако он дал Невельскому очень осторожную инструкцию. В ней речь шла не об Амуре, а о юго-восточном побережье Охотского моря, которое позволялось осмотреть, выдавая своё появление в том районе за случайное. 21 августа "Байкал" покинул кронштадтский рейд.
Пока судно огибало земную поверхность, в Петербурге началась борьба между двумя партиями, придерживавшимися разных политических взглядов. Одна, включавшая Нессельроде, министра финансов графа Ф.П. Вронченко и графа В.Н. Панина, ориентировалась на Европу и считала отношения с нею основой российской внешней политики. Другая, объединявшая Меншикова, графов Л.А. и В.А. Перовских, а также графа П.Д. Киселева, склонялась к более самостоятельному политическому курсу, подразумевавшему активное проникновение в Азию. Поэтому когда в январе 1849 года Муравьёв представил правительству записку о необходимости занять устье Амура, дабы опередить там англичан, и утверждал, что владеющий им будет владеть и всей Сибирью до Байкала. Нессельроде попытался свести дело к постепенному сближению с гиляками. Однако благодаря усилиям его противников записка послужила поводом к учреждению Особого комитета для обсуждения застарелой проблемы. Постоянными членами Амурского комитета были назначены Нессельроде, Меншиков, военный министр светлейший князь А.И. Чернышёв, граф Л.А. Перовский и граф Ф.Ф. Берг. Комитет нашёл заявление Муравьёва об опасности появления иностранцев близ устья Амура достаточно обоснованным. Для предупреждения её было предложено наладить через Российско-американскую компанию связи с гиляками. Невельскому разрешалось занять в непосредственной близости к устью реки какой-либо пункт, всячески избегая столкновений с китайцами. Последнее, пожалуй, было излишним, так как потрёпанный в войне с англичанами Китай переживал смуту и не мог угрожать России. Император Николай I утвердил постановления комитета, однако прошло ещё несколько месяцев, прежде чем они были воплощены.
В начале 1849 года "Байкал" обогнул мыс Гори, а 12 мая, преодолевая снежные заряды, вошёл в Авачинскую бухту. С этого момента Невельской поступил в распоряжение восточно-сибирского генерал-губернатора. В Петропавловске капитан-лейтенанта ожидало письмо Муравьёва, с приказанием сдать груз на транспорт "Иртыш", и две инструкции. Одна предписывала Невельскому осмотр берегов Охотского моря. Другая же, секретная, прямо указывала на устье Амура. В случае необходимости командиру "Байкала" рекомендовалось ссылаться на то, что российские суда часто появляются в тех местах, так как считают Северный Сахалин своим, но для сведения сообщалось, что северная часть острова принадлежит Китаю, а южная - Японии. Муравьёв предупреждал Невельского, что ему оставлена копия инструкции, отправленной на утверждение в Петербург. Однако капитан-лейтенант опасался пропустить благоприятное для экспедиции время и не стал дожидаться подлинника. 30 мая "Байкал" поднял якорь и взял курс на Сахалин.
Берега острова моряки транспорта увидели 12 июня, и сразу же отметили неточность карты, составленной Крузенштерном. Из-за плавучих льдов войти в амурский лиман судну удалось только 27 числа, но Невельской умело распорядился оставшимся временем. Опись и промеры продолжались с утра до вечера, нередко в плохую погоду. Вскоре стало очевидным, что Сахалин - остров, вход в лиман с юга доступен любым судам, а с севера - имеющим осадку до 23 футов (7 м). В саму же реку вели два фарватера: северный, с глубиной 12 футов (3,6 м), и южный, 15-футовый (4,5 м). Завершив промеры, Невельской 30 августа покинул воды Татарского пролива и 3 сентября прибыл в Аян, где застал возвращавшегося с Камчатки Муравьёва. Генерал-губернатор с энтузиазмом воспринял доклад командира "Байкала" и приказал ему выехать в Петербург, чтобы представить результаты исследования высшему начальству. Кроме того, для предварительного уведомления князя Меншикова курьером в столицу немедленно был послан М.С. Корсаков.
Видимо, успех экспедиции задел за живое Нессельроде, и он сразу по получении в Петербypге известия об её достижениях потребовал разжаловать Невельского в солдаты за уход из Петропавловска без формального разрешения. Однако происки канцлера не принесли плодов: император
Николай I не только снисходительно отнёсся к проступку офицера, но и повысил его в чине. Нессельроде удалось лишь воспрепятствовать скорой реализации планов Невельского, отразившихся в рапорте генерал-губернатора Восточной Сибири от 1 января 1850 года. Соглашаясь со взглядами командира "Байкала", Муравьёв писал о необходимости скорее занять устье Амура, чтобы помешать иностранцам обосноваться там, а также чтобы получить в своё распоряжение пути сообщения сибирских губернии с Охотском и Петропавловском, позволяющие содержать в этих портах сильный боевой флот. Первым же шагом, гласил рапорт, должно быть основание военного поста, контролирующего вход в реку, которое следует поручить Невельскому. Представление Муравьёва поступило в Амурский комитет, рассмотревший его и 3 февраля постановивший ограничиться для начала устройством средствами Российско-американской компании торгового зимовья в заливе Счастья, севернее амурского лимана.
Такое компромиссное решение не устроило генерал-губернатора, и он 18 марта обратился непосредственно к государю. Но тот передал ходатайство в Амурский комитет, из дипломатических соображений переименованный в Гиляцкий. Комитет же вновь высказался против активных действии. Его позиция, во многом определяемая Нессельроде, сводила на нет значение усилий Муравьёва и Невельского, так как постановление об основании зимовья было близко к исполнению. Командир Аянского порта Российско-американской компании, капитан 1 ранга B.C. Завойко ещё 12 июля 1849 года отправил в залив Счастья отставного штурмана Д.И. Орлова с четырьмя сотрудниками и товарами для меновой торговли с гиляками. Выгодно распродав товары, Орлов вернулся в Аян, а 1 мая 1850 года был вторично послан на прежнее место. Там его и нашел Невельской, прибывший в залив 27 июня на транспорте "Охотск". Высадившись на берег, начальник экспедиции не замедлил подчинить Орлова, и вопреки расчётам Нессельроде оставил Российско-американской компании вспомогательные функции, преимущественно источника снабжения.
Зимовье, названное Петровским, уже строилось, когда гиляки сообщили Невельскому, что минувшей весной в южной части Татарского пролива побывали три иностранных судна, занимавшихся промерами. Это известие встревожило его и побудило, вопреки инструкции, отправиться в устье Амура на шлюпке с шестью вооружёнными матросами и двумя гиляками-переводчиками. Поднявшись на сотню вёрст вверх по реке, Невельской осмотрел берега и 1 августа 1850 года водрузил Андреевский флаг близ мыса Куегда, тем самым учредив Николаевский военный пост. Он говорил с местными жителями, изъявившими желание поступить в российское подданство, и, возвращаясь в Аян, взял с собой двух делегатов, уполномоченных подтвердить эту просьбу высшему начальству. Действия Невельского получили полное одобрение генерал-губернатора. Иначе отнёсся к ним Гиляцкий комитет, заслушавший соответствующую записку Муравьёва, доставленную им лично в ноябре месяце. Председательствовавший в комитете Нессельроде заявил, что основание Николаевского поста и предложение о принятии в подданство гиляков преждевременны, более того, опасны, так как могут вызвать столкновение с китайцами. Его позицию разделили князь Чернышёв и директор Азиатского департамента Л.Г. Сенявин, на сторону же Муравьёва стали князь Меншиков и граф Перовский. Канцлер вновь потребовал разжаловать Невельского, но Муравьев сумел отстоять сотрудника на аудиенции у Николая I.