В морях европейских
Три года учёбы в офицерских классах, и мичман Невельской, успешно сдавший экзамены, произведён в лейтенанты. Его назначили в эскадру Ф. Литке на фрегат «Беллона», которым командовал капитан-лейтенант С. Мофет, плававший вокруг света вместе с Литке на корабле «Моллер» капитана М.Н. Станюковича. Невельской исходил на «Беллоне» всё Балтийское море. Довелось ему участвовать также в рейдах вокруг Скандинавского полуострова и в Средиземном море.
Это была обычная, рутинная морская служба, повышения в звании Невельской долго не получал, назначение в дальнее плавание, о котором мечтал, не приходило. Недоброжелатели объясняли это тем, что он-де не вышел ростом: внешний вид юного моряка не произвёл должного впечатления на наследника престола великого князя Константина, под флагом которого выступала эскадра адмирала Литке.
Однако 1846 год в жизни Невельского оказался поворотным. В 33 года, по завершении плавания в Средиземном море, через десять лет после окончания офицерских классов, на семнадцатый год морской службы, Геннадий Невельской получил звание капитан-лейтенанта. Одновременно он был назначен на фрегат «Паллада», строительство которого шло к окончанию. Пока же начальство направило Невельского на Чёрное море для осмотра условий стоянки кораблей в Севастополе и Николаеве. Он вернулся с обстоятельным докладом.
12 августа 1846 года умер И.Ф. Крузенштерн, которого считали своим учителем все русские мореходы того времени, и прежде всего Литке, подростком взятый Крузенштерном на «Надежду». Литке стал фактическим руководителем учреждённого при участии Крузенштерна Русского географического общества.
В это время Невельской, вместо того чтобы с восторгом принять предложение командовать «Палладой», неожиданно обратился к генерал-адмиралу великому князю Константину, командующему Военно-морским флотом России, с просьбой назначить его командиром не на генерал-адмиральскую «Палладу», а на строившийся в Финляндии скромный транспорт «Байкал», направлявшийся на Камчатку с грузом для российских колоний в Америке. Невельского поддержал Литке. Для окружающих это выглядело как отказ от наконец-то открывшейся перед моряком перспективной карьеры. Но для самого Невельского то была единственная возможность осуществить давнюю мечту — исследование устья Амура. Он был убеждён, что Амур судоходен в своём устье: «Неужели такая огромная река, Амур, не могла проложить для себя выхода в море и теряется в песках?..»
Получив согласие, Невельской сразу же направил в Главный морской штаб рапорт с просьбой разрешить ему провести исследование Амурского лимана и юго-восточного побережья Охотского моря.
Просьба не была одобрена. Невельскому предложили использовать для производства описи морских берегов только то время, которое удастся сэкономить после выполнения основной задачи — доставки грузов. Но это его не остановило.
Невельской хотел отправиться на «Байкале» как можно быстрее, ему не терпелось приступить к исполнению своего плана, он интуитивно чувствовал, что это главное дело его жизни.
Транспорт «Байкал» предполагалось спустить на воду на верфях Боргстрема в Гельсингфорсе в сентябре 1848 года. Но Невельской не хотел ждать так долго: если выйти в плавание поздней осенью, не останется времени на исследовательскую работу в устье Амура и на Сахалине. Он добился с помощью Литке приёма у начальника Главного морского штаба А.С. Меншикова и получил разрешение ускорить строительство судна и его отправку в плавание.
Затем Невельской встретился с только что назначенным генерал-губернатором Восточной Сибири графом Н.Н. Муравьёвым (получившим позднее приставку к своей фамилии — Амурский). Осознав важность предлагаемого проекта, молодой губернатор обещал оказать ему полную поддержку.
Невельской немедленно выехал в Гельсингфорс, где передал на верфь, строящей «Байкал», приказ о переносе сроков его спуска на воду с сентября 1848 года на июль. Для постоянного наблюдения за ходом строительства в Гельсингфорсе остался старший офицер «Байкала» лейтенант Пётр Казакевич, тоже выпускник кадетского корпуса.