Уже с ранних лет он отличался энергичным характером, блестящими способностями и развитым чувством долга. Начиная с 1829 года Невельской каждое лето отправлялся в плавание. Вначале он плавал на кораблях корпусной эскадры, а затем на кораблях «Михаил», «Прохор», «Кульм».
Чтобы усовершенствовать свое образование, Геннадий, получив звание мичмана, поступил в «высшие офицерские классы», которые стали вскоре Морской академией. В 1836 году он закончил эти классы, получил звание лейтенанта и назначение на корабль «Беллона».
Назначение на «Беллону» было весьма лестным, так как именно на этом судне 9-летний генерал-адмирал Российской империи Константин, сын Николая I, обучался морскому делу. Ему очень понравился молодой и жизнерадостный офицер Невельской.
Последний стал сопровождать великого князя Константина и его наставника, путешественника Ф.П. Литке, в их плаваниях.
Но одновременно Невельской мечтал отправиться в самостоятельное путешествие. Как-то он узнал, что в плавание на Камчатку отправляется большая шхуна «Байкал», которая должна была отвезти туда снаряжение и адмиралтейские запасы для дальневосточных гарнизонов. Невельской стал хлопотать, к некоторому неудовольствию великого князя, чтобы его назначили капитаном «Байкала», и его действительно назначили капитаном в 1847 году, в возрасте 34 лет.
Сие назначение многим казалось странным. Ведь Невельской, к которому очень благоволил Константин, мог сделать блестящую морскую карьеру, но пренебрег этим, сломав ее своим назначением на транспорт «Байкал». Многие, зная энергичность Невельского (который из-за этого получил кличку «неистовый Геннадий»), считали этот поступок его очередной причудой, о которой он, одумавшись, очень пожалеет.
Однако все, кто так считал, на самом деле ошибались. Решение Невельского было вполне обдуманным. К тому же он тщательно изучил историю открытия первыми землепроходцами Камчатки и Приамурья и своей целью в путешествии поставил изучение устья Амура.
Геннадий Иванович очень надеялся после сдачи груза в Петропавловске получить разрешение отправиться на «Байкале» в Охотское море для исследования там устьев Амура.
Но сразу же начались трудности, ибо к планам Невельского резко отрицательно отнесся начальник главного морского штаба князь Меншиков. Он боялся гнева Николая I и не хотел ссориться с графом Нессельроде, пользующимся тогда большим влиянием.
По существующей субординации Геннадий Невельской не имел возможности выполнить свое намерение. Но ему удалось убедить строителей «Байкала» ускорить работы на 2 месяца; это время могло бы быть использовано для исследований.
Однако Меншиков упирался и не разрешал дополнительный поход. А Невельскому обязательно нужно было получить разрешение, за самовольные действия его могли сурово наказать и могло пострадать все предприятие, чего Невельской не допускал.
Геннадию Ивановичу удалось заинтересовать проблемой устья Амура генерал-губернатора Восточной Сибири Н.Н. Муравьева. При содействии его и министра внутренних дел В. Перовского Невельскому удалось добиться согласия Меншикова на экспедицию.
Теперь Геннадий Иванович составил для себя инструкцию, которую нужно было представить Николаю I и добиться его «высочайшего соизволения».
Невельской не хотел терять времени на согласования, а потому ушел в плавание. Предварительно он условился с Муравьевым, что тот утвердит у царя инструкцию, а потом пришлет ее в Петропавловск-на-Камчатке.
«Байкал» взял курс из Кронштадта на Камчатку 28 августа 1848 года.
Невельской не знал, что над его экспедицией нависла опасность. А дело обстояло следующим образом.
8 февраля 1848 года по инициативе графа Нессельроде и «за спиной» Муравьева была утверждена сухопутная экспедиция на Дальний Восток под руководством подполковника генерального штаба Ахте. Последнему было поручено обследовать и наметить «будущую границу», которую Нессельроде предполагал провести гораздо севернее Амура.
Муравьев ничего не знал об этой экспедиции и не мог помешать действиям Ахте, который прибыл в Иркутск во время инспекционной поездки губернатора на Камчатку.
Но Муравьев в дороге получил известие о деятельности экспедиции Ахте и пошел на рискованный шаг, приостановив ее работу.
Так, вместе с инструкцией Ахте была составлена и инструкция Невельскому, да и то под нажимом Муравьева и Перовского. Однако по ней Геннадий Иванович имел право лишь отыскать на Амуре пункт, «который со временем можно было бы занять, если бы таковое предприятие было признано своевременным».
Но Невельской даже на таких условиях не собирался отказываться от своей затеи.
«Байкал» прибыл в Петропавловск-Камчатский в мае 1849 года. Груз был доставлен в полной сохранности, а в канцелярии порта Невельского ждал пакет. В нем находилась лишь копия инструкции, подлинник которой после утверждения обязывались прислать на Камчатку.
Но шло время, а инструкции все не было, и тогда Невельской решился на самостоятельное плавание. 30 мая «Байкал» взял курс на Сахалин.
В первые же дни плавания стало ясно, что район Охотского моря нужно заново картографировать.