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