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

Гавриил Андреевич Сарычев был лишь одним из трёх помощников Биллингса. Другими были англичанин Роберт Галл и Христиан Беринг. Всего же в экспедицию отправились 141 человек. Всем обещано было двойное жалованье, офицерам по достижении устья Колымы — производство в следующий чин, а у берегов Северной Америки — и последующий.

Сарычев с двумя мастеровыми выехал из Петербурга 12 сентября 1785 года, раньше других членов экспедиции, чтобы подготовиться к строительству судов в Охотске. Через неделю он был в Москве, а 10 ноября, через два месяца, уже в Иркутске, проехав на перекладных всю Сибирь. Ещё через два месяца, 10 января 1786 года, прибыл в морозный Якутск на санях, запряжённых низкорослыми местными лошадьми. 10 января 1786 года Сарычев достиг этого города, поставленного на левом берегу Лены 135 лет назад. Старинное деревянное здание острога-крепости ещё сохранилось, вокруг него разместились юрты якутов и жилые дома с маленькими окошками, в которые вставлены были где слюда, где бычьи пузыри, а где просто льдины, крепко примороженные в косяки облитым водой снегом. Жители города — казаки, чиновники, купцы, ссыльные преступники — жили вольно, без охраны, но тем не менее ничего не слышно о «каких-либо от них шалостях».

Сарычева отговаривали ехать в Охотск в самый разгар суровой зимы, но он, запасшись продуктами на два месяца и «тёплым оленьим платьем», отправился 22 января с верховыми и вьючными лошадьми. Проводники-якуты вели их, связанных по десять, друг за другом. Для переговоров с якутами и тунгусами взят был казак, знавший оба местных языка. Ночевали в юртах у зажиточных якутов, назначенных в каждом улусе старшинами («князьками»). Сарычев писал, что «гостеприимство у якутов есть первая добродетель: не успеешь приехать к селению, как они уже встречают, помогают сойти с лошади и ведут в юрту, раскладывают большой огонь, снимают с приезжего платье и обувь, очищают снег и сушат... и стараются услужить сколько возможно».

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

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

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

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

В середине мая, когда река освободилась от ледяного покрова, спустили на воду оба судна — сначала «Паллас», а потом и «Ясашну». Взяв запас продовольствия на семь месяцев, 25 мая оба корабля пошли вниз по Колыме к Северному Ледовитому океану. Через неделю они достигли устья реки Омолон. На одном из его притоков, Омолонской Мангазейке, стояли развалины постройки первопроходцев этих мест; неведомые люди проплыли с Лены на Колыму по Ледовитому морю и по Колыме — к Омолону и его верховьям.

У впадения в Колыму двух рек — Большого и Сухого Анюя — путешественники были свидетелями массовой переправы через реку большого стада диких северных оленей. Олени кочевали к морскому побережью, спасаясь от комаров (в конце лета они будут возвращаться обратно).

Юкагиры используют миграцию оленей для охоты, и Сарычев описал впечатляющую картину боя оленей, плывущих через реку. Участники экспедиции тоже провели заготовку мяса, которым им не удалось запастись до отъезда в Нижнеколымске.

По берегам Колымы попадались следы пребывания здесь первопроходцев: зимовье Шалаурова, пытавшегося пройти из устья Колымы к Берингову проливу на судне «Вера. Надежда. Любовь». Оно было построено через 30 лет после того, как Дмитрий Лаптев поставил свой маяк в устье Колымы. Маяк сохранился: прошло не так уж много времени — всего полвека.

Сарычев определил точные координаты устья Колымы. Удастся ли на сей раз пройти дальше на восток? 24 июня суда вышли в океан. Но уже на следующий день ветер погнал льды. Они прижимали корабли к берегу, сужая до предела канал чистой воды. Пришлось остановиться на три дня. Продвинулись немного и снова вынуждены были бросить якорь.

С большим трудом добрались до мыса Баранов Камень, где стоял крест, поставленный, по-видимому, очень давно, возможно, ещё когда шли на своих кочах к Берингову проливу Семён Дежнёв и Федот Алексеев. Грустная картина открылась с высокого мыса: всё пространство на северо-востоке заполняли льды.

Вряд ли возможно дальнейшее продвижение, решили Биллингс и Сарычев.

Суда возвратились к Колымскому устью. Вторая попытка пройти на восток, предпринятая в июле, также не принесла успеха. Вернулись к мысу Баранов Камень. Здесь состоялось совещание офицеров экспедиции, на котором было принято решение «за невозможностью в виду... великих льдов следовать далее и за поздним временем возвратиться назад». Кто-то предложил пересечь Чукотку на собаках, но тотчас возник вопрос: чем кормить собак?

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

Чукчи поведали о земле на Севере, до которой надо добираться по морским льдам. Сарычев первый сообщил о возможности обнаружения острова, впоследствии названного островом Врангеля.

Разделились на два отряда: сотник Иван Кобелев с чукчей Николаем Дауркиным отправились в Гижигу, все остальные — в Якутск. Из Якутска Биллингс послал несколько отрядов: штурман С. Бронников собрал первые сведения о нагорье, разделяющем реки Мая и Юдома бассейна Алдана. Геодезист сержант О. Худяков произвёл съёмку долины Колымы, а потом вместе с А. Гилевым на байдаре обследовал Курильские острова и от Камчатки проплыл к острову Кадьяк, близ Аляски; они открыли и описали несколько островов из Алеутской гряды.