Это была обычная, рутинная морская служба, повышения в звании Невельской долго не получал, назначение в дальнее плавание, о котором мечтал, не приходило. Недоброжелатели объясняли это тем, что он-де не вышел ростом: внешний вид юного моряка не произвёл должного впечатления на наследника престола великого князя Константина, под флагом которого выступала эскадра адмирала Литке.

Однако 1846 год в жизни Невельского оказался поворотным. В 33 года, по завершении плавания в Средиземном море, через десять лет после окончания офицерских классов, на семнадцатый год морской службы, Геннадий Невельской получил звание капитан-лейтенанта. Одновременно он был назначен на фрегат «Паллада», строительство которого шло к окончанию. Пока же начальство направило Невельского на Чёрное море для осмотра условий стоянки кораблей в Севастополе и Николаеве. Он вернулся с обстоятельным докладом.

12 августа 1846 года умер И.Ф. Крузенштерн, которого считали своим учителем все русские мореходы того времени, и прежде всего Литке, подростком взятый Крузенштерном на «Надежду». Литке стал фактическим руководителем учреждённого при участии Крузенштерна Русского географического общества.

В это время Невельской, вместо того чтобы с восторгом принять предложение командовать «Палладой», неожиданно обратился к генерал-адмиралу великому князю Константину, командующему Военно-морским флотом России, с просьбой назначить его командиром не на генерал-адмиральскую «Палладу», а на строившийся в Финляндии скромный транспорт «Байкал», направлявшийся на Камчатку с грузом для российских колоний в Америке. Невельского поддержал Литке. Для окружающих это выглядело как отказ от наконец-то открывшейся перед моряком перспективной карьеры. Но для самого Невельского то была единственная возможность осуществить давнюю мечту — исследование устья Амура. Он был убеждён, что Амур судоходен в своём устье: «Неужели такая огромная река, Амур, не могла проложить для себя выхода в море и теряется в песках?..»

Получив согласие, Невельской сразу же направил в Главный морской штаб рапорт с просьбой разрешить ему провести исследование Амурского лимана и юго-восточного побережья Охотского моря.

Просьба не была одобрена. Невельскому предложили использовать для производства описи морских берегов только то время, которое удастся сэкономить после выполнения основной задачи — доставки грузов. Но это его не остановило.

Невельской хотел отправиться на «Байкале» как можно быстрее, ему не терпелось приступить к исполнению своего плана, он интуитивно чувствовал, что это главное дело его жизни.

Транспорт «Байкал» предполагалось спустить на воду на верфях Боргстрема в Гельсингфорсе в сентябре 1848 года. Но Невельской не хотел ждать так долго: если выйти в плавание поздней осенью, не останется времени на исследовательскую работу в устье Амура и на Сахалине. Он добился с помощью Литке приёма у начальника Главного морского штаба А.С. Меншикова и получил разрешение ускорить строительство судна и его отправку в плавание.

Затем Невельской встретился с только что назначенным генерал-губернатором Восточной Сибири графом Н.Н. Муравьёвым (получившим позднее приставку к своей фамилии — Амурский). Осознав важность предлагаемого проекта, молодой губернатор обещал оказать ему полную поддержку.

Невельской немедленно выехал в Гельсингфорс, где передал на верфь, строящей «Байкал», приказ о переносе сроков его спуска на воду с сентября 1848 года на июль. Для постоянного наблюдения за ходом строительства в Гельсингфорсе остался старший офицер «Байкала» лейтенант Пётр Казакевич, тоже выпускник кадетского корпуса.

Транспорт «Байкал» спущен был на воду 10 июля 1848 года, а 20 июля он уже стоял на кронштадтском рейде, 21-го августа буксиром его вывели за Толбухин маяк, откуда и началось самостоятельное плавание. На борту находил ось-8 офицеров и 38 унтер-офицеров и матросов.

Невельской стремился дойти до Камчатки как можно быстрее, чтобы выкроить время для исследовательской работы. Но приходилось считаться с погодой. Первый шторм настиг в Балтийском море, и из-за него двое суток простояли под прикрытием острова Соскор, до Копенгагена добирались две недели. А в датских проливах ветер был слишком слабым — опять задержка.

Зато из Портсмута курс был взят сразу на Рио-де-Жанейро без захода на Азорские острова, и ровно через два месяца крупнейший порт Южного полушария приветствовал «Байкал» «салютом наций» — 21 залп.

Первого декабря плавание продолжилось. Предстоял труднейший участок пути — обход с юга материка Южной Америки вокруг вечно окружённого штормами мыса Горн.

Среди бурных волн, под студёным дыханием Антарктики моряки встретили на «Байкале» Новый, 1849 год. Только 10 января был пройден меридиан мыса Горн, и корабль вошёл в Тихий океан. Через месяц он уже был в чилийском порту Вальпараисо, затем — два месяца плавания в удивительно спокойном океанском просторе. Наконец пассатные ветры доставили парусник на Сандвичевы (Гавайские) острова, в порт Гонолулу, где на рейде стоял русский транспорт «Иртыш». Вместе с земляками «байкальцы» провели на Гавайях православную пасхальную неделю, хотя и без традиционного посещения храма.

Офицеров с «Байкала» во главе с Невельским принял король Тамеамеа, знакомый уже со многими русскими моряками, чьи корабли заходили на гостеприимные Сандвичевы острова. Приём был исключительно дружеским, но задерживаться было нельзя. Как только завершилась Пасха, «Байкал» ушёл в океан, направившись теперь уже непосредственно к Камчатке. Распрощавшись с тепличными условиями тропиков, моряки оказались в обстановке северных штормов и туманов. Камчатка, которой судно достигло в начале мая, встретила настоящей зимней погодой. Густой снегопад засыпал палубу «Байкала», как только он вошёл в Авачинскую бухту.

Это был рекордно ранний для Петропавловска приход корабля из России, обычно они появлялись на рейде местной гавани лишь осенью.

Невельской, выйдя из Кронштадта в конце лета, преодолел путь через три океана за 8 месяцев и 23 дня. Только Головнин в своё время на более быстроходном шлюпе «Камчатка» пришёл на две недели быстрее.

Часть груза, предназначенного для Охотска, с «Байкала» перегрузили на «Иртыш». Это освободило Невельского от необходимости заходить в Охотск. Он смог прямо направиться к Сахалину, согласно инструкции, написанной генерал-губернатором Н.Н. Муравьёвым.

Огорчало только то, что пока не пришло из Петербурга утверждение инструкции императором. Но Невельской не стал дожидаться, и как только на «Байкал» погрузились три алеута со своими байдарками для плавания в прибрежном мелководье, Петропавловск был оставлен.

Невельской обратился к офицерам корабля: «...На нашу долю выпала столь важная миссия, и я надеюсь, что каждый из нас честно и благородно исполнит при этом долг свой перед отечеством».

2 июня судно вышло из Авачинской бухты, через пять дней пересекло по Четвёртому Курильскому проливу островную гряду Курил, слегка задерживаясь из-за безветрия. Охотский берег был измерен — астрономический пункт с координатой 51°40' с. ш. — как раз в том месте, где более 40 лет назад Крузенштерн попал в «сулой» — неприятное столкновение приливо-отливных течений, из-за чего шлюп «Надежда» не смог пройти в Татарский пролив. Тогда так и не удалось выяснить, соединён ли Сахалин с материком.

Транспорт «Байкал» подошёл к берегу в ночь с 11 на 12 июня. Как только забрезжил рассвет, Невельской напряжённо стал всматриваться в контуры низменного берега, за которым виднелось водное пространство, а далее — заснеженные сопки.

Невельской настойчиво начал искать признаки Амура. К берегу отправились алеутские байдары, но им не удалось приблизиться к суше. Алеуты сообщили только, что обнаружен залив, в котором много китов. Отправились вельбот и шлюпка с офицерами «Байкала» во главе с Петром Казакевичем. На этот раз берег был достигнут и произошла встреча с местными жителями — гиляками. Они ничего не знали об Амуре: он где-то далеко и залив к нему не ведёт, но на песке начертили другую реку, которая впадала в лиман. Возможно, Амурский.