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