Пространная инструкция, данная губернатором «для описания и осмотру сысканного Чиракиным через Новую Землю пролива», подробно определяла задачи будущего плавания. В ней предписывалось: «...прибыв к оному Карскому проливу и оный пролив с частями земли, которую видеть можете, положить на карту, и того пролива глубину измерить и в какой те острова и пролив широте, и за проливом какое положение местам — описать; и буде возможно будет и большим судном пройтись сквозь оной, то и в том старание употребить...
Бели же, по благости Божией и по переходе через оной пролив, по осмотру Вашему, найдется за тем проливом море, мореплаванию способное, и льдов нет, но невозможно-ль будет до устья Оби реки иметь таковыми судами способный проход; все то подробно приметить и описать. А буде расстояние недальнее окажется, то не будете-ль вы в состоянии на оном судне и в Обь реку войти: и ежели препятствия в том не найдется, то, склоня к тому пристойным образом кормщика и работников, — до Обского устья, или сколько глубина той реки позволит; а буде не можно, то хотя и до губы вояж предпринять... За тем проливом во время вояжа к устью Оби реки буде увидите, и то обстоятельно описать, какие суда, отколь и куда, и с чем и какими местами ходят...»
Через неделю после начала плавания с борта коча открылась Гусиная Земля, а 15 августа судно вошло в Маточкин Шар. Здесь, в устье одной из рек, была найдена старая промысловая изба. В предвидении зимовки избу в разобранном виде погрузили на судно — в добавление к уже имевшейся захваченной из Архангельска. «И в том рассудилось, — записал в журнале начальник экспедиции, — дабы поставить оныя в разных местах для лучшего промыслу».
Опасаясь мелей, в дальнейший путь Розмыслов отправился на шлюпке, с которой провел промер вплоть до мыса Моржов. В последующие дни он преодолел путь до восточного выхода из Шара. Весь маршрут до устья реки Шумилихи был положен на карту и подробно описан. Однако выйти в Карское море не удалось. «Противные ветры к тому не допускают»,— отметил штурман в своем журнале. На востоке Шара в качестве места для зимовки Розмыслов избрал залив обширной Белужьей губы, названный им Тюленьим, «ибо множество тут находится плавающих стадами морских зверей, белух и разных родов тюленей».
На время зимовки путешественники разделились на две равные группы. Первая, во главе с Розмысловым и Чиракиным, осталась на берегу Тюленьего залива в привезенной промысловой избе. С наступлением холодов люди «законопатили избные окна от нестерпимости снегов и крепких ветров». Избу, привезенную из Архангельска, штурман Матвей Губин с шестью работниками поставил на берегу Шара, у Дровяного мыса.