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

Снова Невельской стоит на капитанском мостике «Байкала»: вместе с Дмитрием Орловым и командой из 15 человек он отправляется в рекогносцировочный поход вокруг Сахалина. Отыскивая удобные бухты на побережье острова, он посетил Императорскую гавань. Удобных бухт на Сахалине не оказалось, а в Императорской гавани Невельской открыл Константиновский пост и оставил охранять его восемь казаков во главе с унтер-офицером Дмитрием Хороших.

В августе прибывший в Николаевский пост Невельской с большой радостью встретился с Бошняком, поведал своему ближайшему помощнику о дальнейших планах, о том, что начальником Константиновского поста в Императорской гавани предстоит быть именно ему. Николаевский пост за два года строительства уже стал походить на город (во всяком случае, в нём появилась первая улица). Продолжать превращение поста в город Николаевск (так уже его стали звать) будет мичман Г. Разградский. Вскоре Бошняк прибыл в Петровский пост, но Невельского там не застал: тому пришлось ехать в Аян за продовольствием и снаряжением для Сахалинской экспедиции, хотя это должен был делать Буссе.

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

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

Эта энергия и горячность не очень нравились майору Буссе, но вскоре и он должен был признать: именно благодаря энергии и настойчивости Невельского Россия сохранила огромную территорию Приамурья и защитила её во время Крымской войны.

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