Второй поставленный им вопрос -- морской -- преследовал цель отыскания удобных защищенных гаваней на побережье Татарского пролива, которые были бы связаны удобными внутренними путями с Амуром и Уссури. Такие гавани и пути и были обнаружены, описаны и положены на карту.
Невельской вменял в обязанность своим сотрудникам обращаться с местными жителями дружелюбно, он требовал не вмешиваться в их жизнь, обычаи и верования и, знакомя их с русской культурой, отнюдь не навязывать силой чуждые им обычаи. Этим было достигнуто установление самых дружеских отношений; население нижнего Амура действительно видело в русских своих защитников, и потому Н. Н. Муравьев, спускаясь в 1854 году с первым сплавом вниз по Амуру, с удивлением отмечал, что ниже устья Сунгари он и его спутники попали в страну, как бы давным-давно принадлежавшую России. Приём, оказанный ему, был весьма дружественным, в то время как выше Сунгари, куда не распространял свою деятельность Невельской, население, завидя шедшие сплавом суда, разбегалось. Дружелюбие народов Приамурья было результатом внимательного и человечного отношения к ним Невельского и его сотрудников, которые привили этим народам первые навыки к земледелию, лечили их и обучали детей грамоте.
Жизнь на песчаной кошке в заливе Счастья, который был открыт Невельским во время плавания в 1849 году, была нелегка: не было достаточного количества свежих продуктов, не было теплой одежды и обуви. Дома, построенные из сырого леса, при постоянных, насыщенных влагой, туманах летом и зимой и большом количестве летних осадков во время муссонных дождей, были сырыми. Вдобавок, не было стекол, окна были закрыты миткалем, зимой из-за этого в домах было очень холодно. Люди от стужи, недоедания и тяжелых изнурительных поездок по неизвестному бездорожному краю болели зимой цынгой.
Российско-Американская компания, задетая успехами Невельского на Амуре, охарактеризованном её работниками в самых чёрных красках, как бесполезной для России реке, готова была придраться к любому случаю, чтобы недодать, недослать, одним словом, насолить "противнику". Так, в 1852 году, считая, что суммы, отпущенные правлению компании для снабжения Амурской экспедиции, уже израсходованы, она отдала распоряжение начальнику своей Аянской фактории и порта А. Ф. Кашеварову не снабжать продовольствием Амурскую экспедицию свыше отпущенных сумм. Поэтому, того не ожидая, Невельской получил такое количество продуктов, которое обрекало его людей на медленную голодную смерть. Невельской жалуется, требует внимания к своим нуждам, указывает справедливо, что в результате всех этих недоразумений страдать будут не только люди, но и дело; однако он вместе с тем великолепно сознает, что его письма -- глас вопиющего в пустыне, что помощи ждать неоткуда. В результате от голода и недоедания гибнет несколько человек из числа команды, умирает Новорожденная дочь Г. И. Невельского. Мучилась и страдала его жена, которая делила с ним все тяготы и неудобства походной жизни и прожила в течение всего срока работы Амурской экспедиции на Петровской кошке и Николаевском посту.
Даже перед лицом надвигающейся катасторфы Невельской не покидает своего поста. Он пишет Муравьёву в сознании безысходности положения полное трагизма письмо: "Когда же мне, и моим благородным сотрудникам, полным самоотверженного сознания своего долга перед Родиной, дадут, наконец, средства для достижения великой государственной цели, которую все мы преследуем, не страшась ни ответственности, ни опасности, ни лишений? Мы верим все, что наступит такая минута, и в надежде на нее с твердостью духа переносим все трудности и опасности, но всему есть предел, переступать который не следует". Даже в таких тяжелых условиях он посылает исследовать Северный Сахалин, учреждает посты в заливе Де-Кастри, в заливе Уанды и других местах; посылает лейтенанта Н. К. Бошняка для изучения побережья Татарского пролива, в результате чего последнему удается изучить и впервые нанести на карту залив -- Гавань императора Николая I (теперь Советская Гавань), одну из крупнейших и удобнейших для стоянки судов гаваней мира.
Жалобы Невельского в Петербург наконец помогли; там поняли, что губить людей из-за личных счетов, возникающих в значительной степени вследствие недоговоренности в переписке, которая велась почти на расстоянии 10 000
"Эти бумаги, -- пишет Невельской, -- были лучом света, озарившим нашу пустыню; они показывали, что правительство, наконец, обратило свое внимание на экспедицию".