Вернулся лейтенант в Петровское лишь 20 июня. Но отдыхать не пришлось.
Генерал-губернатор Восточной Сибири Николай Николаевич Муравьёв велел Невельскому сосредоточить внимание на исследовании побережья Татарского пролива южнее Амурского лимана и Сахалина. Тот немедленно принялся формировать экспедицию.
Осенью 1852 года Невельской отправил на баркасе вдоль побережья мичмана Григория Даниловича Разградского для создания промежуточного склада. Мичман доставил запас продовольствия в селение Кэтово (в последующем — Мариинский пост). Затем начальник Амурской экспедиции послал для исследования береговой черты мичмана Николая Матвеевича Чихачёва на боте.
Но посудина эта совершенно не годилась для плавания, текла как решето. Чихачёв сразу же вернулся. Раздосадованный Невельской приказал отправиться на том же дырявом боте подпоручику корпуса флотских штурманов Дмитрию Ивановичу Орлову. Тот, как мог, привёл его в порядок и вышел в море. Но плоскодонный бот предназначался для плавания только по рекам. На волнении в море его стало бить и захлёстывать волнами. Орлов отошёл на двадцать миль от Петровского и сумел вернуться живым со своей командой только благодаря огромному опыту управления с парусами.
Пока искали другое плавсредство, время для плавания упустили. Тогда Невельской послал зимой 1853 года по тому же маршруту Бошняка. Ему было предписано следовать до селения Кизи, затем перейти в Де-Кастри, взять туземную лодку и весной на ней следовать вдоль берега.
Его сопровождали два казака, Семён Парфентьев и Кир Белохвостов, а также якут Иван Масеев в качестве переводчика. Им выделили три нарты, каждая из которых была запряжена 10 собаками. Общий вес груза составлял 70 пудов. В сутки удавалось пройти не более 25 вёрст.
Когда добрались до селения, где Разградский оставил продовольствие, того, что везли с собой, почти не осталось. К счастью, запасы, привезенные Разградским, оказались целы. Старику по имени Обса, который его охранял, сделали подарок.
Маленький отряд двинулся дальше, к югу. Бошняк приобрёл туземную лодку и поплыл с казаками дальше, осматривая побережье. Он искал залив Хаджи, о котором толковали туземцы. Ночевали в снегу, закутавшись в шубы и дохи из медвежьего меха, кишевшего насекомыми. Когда удавалось переночевать в гиляцкой деревушке, играли с хозяевами в китайские карты или игру, названия которой Бошняк не запомнил: деревянная доска с тремя рядами отверстий, в которые вставлялись фишки. Очерёдность хода определялась бросанием кости. В пути сами пекли на костре хлеб, пополняли припасы рыбой, которую выменивали у гиляков. Подбадривали себя и спиртом, который везли с собой. Он служил к тому же отличной разменной монетой при торгах с гиляками.
