Наступила зима — пришлось потерять несколько недель, чтобы сделать нарты и лыжи для продолжения путешествия на восток. Вскоре, правда, выяснилось, что проводники не знают дороги; стала ощущаться нехватка продуктов, ослабела дисциплина. И без того малочисленный отряд начал таять — несколько человек дезертировало.

После тяжелой зимовки где-то в верховьях р. Большого Ольдоя, притока верхнего Амура (у 123° в.д.), геодезисты решили завершить работы. Они перевалили в верховья р. Нюкжи и со съемкой спустились по ней и по р. Олёкме на р. Лену. В Якутск они добрались в начале июня 1736 г. и представили карты большей части течения р. Нюкжи и нижней Олёкмы.

По приказу В. Беринга геодезистам пришлось повторить поиски дороги на р. Уду. Через Иркутск они прибыли в Нерчинск ц в начале июня 1737 г. во главе более крупного отряда снова направились на восток. На этот раз им удалось достичь верхнего Гилюя. По ноябрьскому снегу на нартах и лыжах они проследили его до впадения в р. Зею и, несомненно, видели хребет Тукурингра, сопровождающий правый берег реки. Целый месяц отряд поднимался по Зее, пока не иссякли запасы продовольствия. К тому же проводники не смогли указать дороги на р. Уду. Пришлось поворачивать назад. Через увалы и холмы в северо-западной части Амурско-Зейского плато геодезисты достигли р. Амура у 124° в.д. и вернулись в Нерчинск в конце декабря.

П. Скобельцын и В. Шетилов не выполнили приказа В. Беринга, но первые пересекли в широтном направлении приамурскую тайгу и «каменные россыпи» южных склонов гор, входящих, как мы теперь знаем, в системы Олёкминского Становика и Станового хребта. По их подсчетам, протяженность маршрута по этой совершенно неисследованной и безлюдной местности с учетом блужданий из-за отсутствия хороших проводников составила 1400 км.

Задача, поставленная В. Берингом, была решена только через 114 лет: от р. Горбицы до р. Уды в 1851 г. прошел топограф В.Е. Карликов.

«Для подыскания известия… имеется ли проход Северным морем», были организованы четыре отряда, получившие отдельные участки северного побережья Азии. Их общая задача заключалась в описи берегов Ледовитого океана от Печорского до Чукотского морей и проверка на практике возможности плавания вдоль берегов Сибири.

Западный отряд должен был пройти по двум трудным для судоходства участкам: проливу Югорский Шар (69°42' с.ш.) — между материком и о. Вайгач — и проливу у 73° с.ш., тогда еще безымянному, — между п-овом Ямал и о. Белым. Отряд получил в Архангельске два новых коча (беломорское плоскодонное судно); одним командовал Степан Воинович Муравьев (он же — начальник отряда), вторым — Михаил Степанович Павлов; экипаж обоих кочей состоял из 51 человека. В конце июля 1734 г. оба судна прошли через Югорский Шар в юго-западную часть Карского моря, в то лето совершенно свободную ото льда, пересекли Байдарацкую губу и поднялись вдоль западного берега Ямала, что по-ненецки означает «край земли», до 72°35' с.ш. 18 августа Муравьев приказал повернуть обратно. Зимовали моряки в устье Печоры, близ Пустозерска. Во время плавания и зимой «почитай все, хотя несколько времени, пребывали тяжкими, головными, грудными и цинготными болезнями, паче горячками, больны», — писал С. Муравьев.

Летом 1735 г. С. Муравьев и М. Павлов повторили попытку. 18 августа они разлучились у северо-западного берега Ямала, затем С. Муравьев достиг 73° 11' с.ш., а М. Павлов — 73°04' с.ш. Оба шли, следовательно, уже вдоль западного берега о. Белого и не заметили в тумане входа в пролив (73° с.ш.) между ним и Ямалом, хотя посланные заранее (зимой) на север казаки зажгли костры у западного входа в пролив и видели суда. Море опять было свободно ото льда, и все-таки оба 23 августа повернули обратно и опять прошли мимо пролива. 9 сентября близ устья Печоры суда соединились, а через две недели остановились на зимовку. С. Муравьев и М. Павлов постоянно ссорились друг с другом, «сильно докучали» местным жителям и скверно обращались с подчиненными. На них поступило много жалоб и доносов, оба были отданы под суд и разжалованы в матросы «за многие непорядочные, леностные и глупые поступки».

Начальником западного отряда назначили Степана Гавриловича Малыгина, человека решительного, крутого и жестокого, но искусного и сведущего моряка, ученого-навигатора. Его помощники — лейтенанты Алексей Иванович Скуратов и Иван Михайлович Сухотин, командуя двумя только что построенными ботами, вышли из Архангельска на восток 22 июня 1736 г. У о. Колгуев сильные встречные ветры на целый месяц преградили им путь. Вынужденную стоянку моряки использовали для съемки острова и лишь 6 августа двинулись дальше. Через два дня они прибыли к о. Долгому, лежащему у входа в Хайпудырскую губу, и доставили суда в распоряжение Малыгина, командовавшего кочем «Обь». Затем флотилия проследовала к проливу Югорский Шар. Выяснив, что для дальнейшего плавания коч не пригоден, Малыгин приказал И. Сухотину вернуться в Архангельск на «Оби», находившейся в аварийном состоянии. 19 августа тот двинулся в обратный путь и выполнил опись побережья Баренцева и Белого морей на протяжении около 2,5 тыс. км от Югорского Шара до Архангельска. На карте, составленной им по материалам съемки, нанесены п-ов Канин, о. Колгуев, отмечены мели и указаны глубины.

Тем временем Малыгин и Скуратов в тяжелой ледовой обстановке (как мы теперь знаем, XVIII в. вообще отличался очень суровыми климатическими условиями) в начале сентября провели боты через Югорский Шар, достигли побережья Ямала и сделали попытку продвинуться к северу. Но льды вынудили их отступить, и 18 сентября суда стали на зимовку в устье р. Кары. 7 ноября 1736 г. к зимовщикам присоединился геодезист Василий Михайлович Селифонтов. Еще весной 1736 г. он проделал на оленях маршрут от устья Печоры через Большеземельскую тундру к устью Оби. Летом он описал восточный берег Ямала, поставил на северном участке несколько маяков и на карбасе осмотрел часть южного побережья о. Белого, а затем прошел вдоль северного и северо-западного берега Ямала, расставил и там маяки до 72°35' с.ш., т. е. до пункта достигнутого Муравьевым. Повернув на юг, Селифонтов проследил всю западную береговую линию полуострова, а также побережье Байдарацкой губы до устья Кары, выполнив съемку побережья протяженностью 1800 км. Он стал первым исследователем Ямала (площадь около 122 тыс. км²): в его журнале дано описание не только прибрежных, но и внутренних районов полуострова.

Выйти в море удалось лишь 6 июля 1737 г. Через 17 дней оба бота вошли в пролив Малыгина между Ямалом и о. Белым, ориентируясь по маякам В. Селифонтова. На плавание мелководным проливом длиной 63 км Малыгин и Скуратов затратили 19 дней. Кроме мелей, движению мешали сильные противные ветры и льды, поэтому только 12 августа удалось обогнуть Ямал. По Обской губе суда двинулись на юг уже с попутным ветром, но прибыли в Березов, на р. Оби, лишь 3 октября. В Петербург Малыгин вернулся весной 1738 г. Скуратов же в начале июля 1739 г. на двух ботах (вторым командовал штурман Марк Головин) направился на запад, проделав морем тот же путь в Архангельск в обратном направлении с зимовкой на р. Каре, причем заснял участок побережья между р. Карой и восточным входом в Югорский Шар. Возвратившись в сентябре 1740 г. в Петербург, он и Малыгин составили первую сравнительно точную карту берегов Баренцева и Карского морей между Архангельском и устьем Оби протяженностью чуть более 4000 км. Впервые на этой карте появляется название «Карское море», данное в память об их зимовках на р. Каре, и изображен п-ов Ямал, об истинных размерах и форме которого до тех пор данных не имелось.