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