Тем временем Невельской, при содействии вице-председателя географического общества, вице-адмирала Ф.П. Литке добился приема у начальника Главного морского штаба (как называлась тогда должность руководителя морского ведомства), генерал-адъютанта светлейшего князя А.С. Меншикова. Князь, уже посвященный в суть дела Муравьёвым и министром внутренних дел графом Л.А. Перовским, тем не менее, отнесся к ходатайству подчинённого скептически. На него, видимо, повлияли уверения Нессельроде, что по Нерчинскому трактату китайцам принадлежат оба берега Амура. И если ускорению постройки "Байкала" начальник Главного морского штаба вполне сочувствовал, подписав соответствующее обращение к владельцам гельсингфорсской фирмы "Боргстрем и К°", то выходить за рамки первоначальной задачи транспорта - доставки продовольствия в Петропавловск - не разрешил. Невельскому пришлось отправить Муравьёву письмо с просьбой о поддержке. Она не заставила себя ждать, однако ничего не изменила. Нессельроде, ссылаясь на высочайшее повеление покончить с амурским вопросом, удержал опытного царедворца Меншикова от самостоятельных действий.
Между тем, об Амуре заговорили в правящих кругах, и канцлеру пришлось выступить с двумя официальными записками, доказывавшими, что Китай владеет левым берегом реки. Нессельроде пугал правительство возможностью дипломатических осложнений из-за Амура и соглашался только на крейсерство у берегов Сахалина одного военного корабля, а лучше судна Российско-американской компании, дабы эта мера казалась частной инициативой. Под воздействием таких аргументов Ментиков отказал командиру "Байкала" и после того, как летом 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.
Выслушав восточно-сибирского генерал-губернатора, император приказал собрать Гиляцкий комитет под председательством наследника, великого князя Александра Николаевича, сочувствовавшего планам Муравьёва. Заседание состоялось 19 января 1851 года. Муравьёв и Меншиков выступили на нём с предложением не ликвидировать Николаевский пост, а заменить его брандвахтой. Однако Нессельроде, Врончснко, Чернышев и Сенявин отрицали целесообразность этой меры, утверждая, что брандвахта не помешает иностранцам утвердиться в устье Амура, но испортит наши отношения с Китаем и погубит кяхтинскую торговлю. Таким образом, канцлер продолжал противиться активизации дальневосточной политики, из соображений равно дипломатических и личных, желая хоть как-то досадить людям, показавшим его несостоятельность в затрагиваемом вопросе. В итоге комитет так и не принял определённого решения. Выбор между двумя мнениями оставался за Николаем I. Император же, рассудив, что там, где поднят русский флаг, он больше спускаться не должен, 3 февраля 1851 года повелел сохранить Николаевский пост. 12 февраля была образована особая, неофициальная Амурская экспедиция, из 60 матросов и 2 офицеров под командованием капитана 1 ранга Невельского. А через три дня в Пекин отправилась нота с предложением начать переговоры о защите амурского устья от проникновения иностранцев.
К тому времени Невельской, приезжавший в Петербург с Муравьёвым, уже возвращался обратно, на берега Тихого океана. В навигацию 1851 года вместе со своими подчинёнными, лейтенантом Н.К. Бошняком, штурманским прапорщиком А.И. Ворониным, а позднее с мичманом Н.M. Чихачёвым и другими офицерами, он обустроил Николаевский пост и Петровское. В последующие годы помощники Невельского, поочерёдно отправляясь в дальние поездки по окрестным землям, исследовали достаточно обширную территорию вокруг устья Амура, включая и его южные берега, ступать на которые формально запрещалось. Постепенно налаживались отношения российских моряков с гиляками и маньчжурскими купцами, доставлявшими по Сунгари и Амуру пшено, рисовую водку, табак, ткани и другие товары. Однако торговля шла не очень бойко, да к тому же требовала больших расходов. Российско-американская компания отнюдь не торопилась снабжать действовавшую под её же прикрытием экспедицию, и последняя нередко страдала от недостатка продовольствия и припасов. Люди болели, умирали. Отчасти их выручали гиляки, снабжавшие черемшой, кореньями, свежей рыбой и олениной. Так шёл месяц за месяцем, но китайцы в низовьях Амура не показывались.
Ссылаясь на это обстоятельство, Муравьёв в январе 1852 года ходатайствовал о преобразовании Амурской экспедиции в правительственную и об увеличении её состава. Против выступил Нессельроде, настаивавший на крайней осторожности действий. Лишь в марте 1853 года, воспользовавшись ухудшением отношений между Россией и западными державами, спровоцированным посольством князя Меншикова в Константинополь, генерал-губернатор сумел добиться своего. Он подал императору обширную записку, в которой помимо уже поставленных вопросов был поднят и вопрос о необходимости заявить свою претензию на весь левый берег Амура. Николай I согласился с большинством предложений Муравьёва, включая предоставление начальнику Амурской экспедиции прав военного губернатора. Но если Невельской ещё в начале того года, на свой страх и риск, распорядился основать посты в заливе Де-Кастри и у озера Кизи, то ведомство Нессельроде всячески затягивало начало переписки с Китаем. Впрочем, нет худа без добра: когда в мае на Амур пришло известие о подготовке американцами двух миссий, дипломатической - в Японию и научной - к северным берегам Тихого океана, начальник экспедиции поспешил выслать людей на юг от Де-Кастри, с приказанием везде объявлять о принадлежности этой территории России. 6 августа 1853 года лейтенант Бошняк основал в заливе Хаджи новый пост, названный Константиновским. Столь самовольные действия, противоречившие инструкциям и взглядам руководителя внешнеполитического ведомства на Нерчинский договор, конечно, болезненно воспринимались последним.
В начале 1853 года правительство решило ради обеспечения безопасности амурского устья занять Сахалин. Невельской, и в этом случае опередивший Петербург, уже посылал на остров Бошняка, осмотревшего к весне 1851 года окрестности залива Дуэ и реки Тыми с богатыми залежами угля. Однако в столице не затухала прежняя борьба партий, и Нессельроде настоял на исполнении решения средствами Российско-американской компании. Её руководство, в свою очередь, предложило поручить это сложное предприятие Невельскому, соглашаясь обеспечить его судами и припасами, а когда дело наладится - передать заведование им своему служащему, лейтенанту И.В. Фуругельму. План компании, изложенный в записке от 13 марта 1853 года, предполагал строительство двух больших укреплений на западном и южном берегах острова, а также нескольких малых. В соответствии с ним Невельской послал на западный берег подпоручика Е.Г. Орлова, 30 августа основавшего Ильинский пост. Однако уже в сентябре, отправившись на Сахалин с основным составом экспедиции, он предпочёл сосредоточить все силы на южной оконечности острова и выбрал местом главного укрепления японское поселение Тамари-Анива. 25 сентября Невельской заложил там Муравьёвский пост и, поручив командование Сахалинской экспедицией майору Н.В. Буссе, вернулся в Петровское.
Занимая Сахалин, Россия затрагивала интересы японцев, около полувека осваивавших его южное побережье. Поэтому вопрос разграничения с Японией на Сахалине и Курильских островах рассматривался учреждённым в начале 1852 года Особым комитетом по азиатским делам, 7 мая постановившим отправить в Страну восходящего солнца посольство во главе с вице-адмиралом Е.В. Путятиным. Важную роль в выработке инструкций послу сыграл известный европейский японовед Ф.Ф. Зибольд, при содействии голландского правительства обратившийся 8 ноября 1852 года в Министерство иностранных дел России с проектом установления русско-японских отношений. Его рекомендации были учтены Нессельроде, предписавшим Путятину выяснить, принадлежит ли южная часть Сахалина Японии, на что тогда можно было получить скорее утвердительный ответ. Адмирал, в октябре покинувший Кронштадт на (фрегате "Паллада", 10 (22) августа 1853 года достиг Нагасаки, но был встречен недружелюбно. После длительного зондажа через голландскую факторию, в январе 1854 года он приступил к официальным переговорам. Однако японцы, настаивавшие на разделении Сахалина по 50° северной широты и границе между островами Уруп и Итуруп, прервали их и возобновили только в декабре, сменив Нагасаки на город Симода.
Между тем, весной 1854 года, ввиду близкого разрыва с Англией и Францией, российское правительство распорядилось перевести все суда, находившиеся в Тихом океане, к устью Амура. Путятину пришлось сделать паузу в переговорах и увести "Палладу" с винтовой шхуной "Восток" в Императорскую гавань, где собрались также корвет "Оливуца", барк "Князь Меньшиков", транспорты "Иртыш" и "Двина", судно Российско-американской компании "Николай". Одним из первых шагов, предпринятых адмиралом, стала эвакуация войск с Сахалина, вызвавшая крайнее недовольство Невельского. Начальник Амурской экспедиции всё ещё думал о закреплении за Россией новых земель, собираясь занять небольшими заставами, по 8-10 человек, все бухты вплоть до устья реки Суйфун, рядом с Корейским полуостровом. Но этот план не получил одобрения начальства, озабоченного безопасностью амурского устья. Действительно, к началу навигации российское командование имело в своём распоряжении всего 25 человек на Петровском посту, 30 - на Николаевском, 8 - на Мариинском (Кизи) и 10 - на Александровском (Де-Кастри). Моряки были вооружены кремнёвыми ружьями. Кроме того, в Николаевске хранились две, а в Де-Кастри одна трехфунтовая пушка, на каждую из которых приходилось по 25 зарядов.
Муравьёв, находившийся тогда в Петербурге, хлопотал об усилении. В начале 1854 года он добился высочайшего разрешения на размещение в устье Амура и в Петропавловске Восточно-сибирского линейного батальона и сотни казаков Забайкальского войска, всего около 700 человек. Для ускорения их передислокации генерал-губернатор предложил воспользоваться путём по Шилке и Амуру. На заседании Амурского комитета, председательство в котором перешло к генерал-адмиралу, великому князю Константину Николаевичу, против этого предложения выступил Сенявин. Однако тревожная обстановка заставила большинство участников согласиться с Муравьёвым. Ему предоставили право договориться с китайскими властями о сплаве войск. 11 января Николай I утвердил положение комитета, и позволил Муравьёву идти по Амуру, не дожидаясь согласия Пекина.
Санкция императора нейтрализовала весьма сковывающую инструкцию, составленную в те же дни для генерал-губернатора чиновниками Министерства иностранных дел. Возвратившись в Иркутск, Муравьёв 14 апреля известил китайское правительство о предоставленных ему правах и о повелении государя выступить на защиту устья Амура от иностранцев. Правящие круги Дайцинской империи с пониманием отнеслись к намерениям своих северных соседей и не стали чинить им препятствий.