Едва вскрылся Иртыш, экспедиция, захватив все свои грузы, села в лодки и поплыла вниз по течению — до впадения Иртыша в Обь. Затем двинулась вверх по Оби — до впадения в Обь реки Кеть. Затем двинулась вверх по Кети — почти до самых истоков. От истоков Кети до Енисейска всего 70 километров. Этот участок пути проехали на лошадях и оказались на берегу Енисея.
Опять перегрузились в лодки и двинулись вверх по Енисею — до впадения в Енисей Ангары. Пошли вверх по Ангаре — до впадения в Ангару Илима. Свернули в Илим. Был уже конец сентября, Илим замерзал. Двигались до последней возможности, но вскоре пришлось остановиться и зазимовать.
Весной следующего, 1726 года, чуть вскрылись реки, двинулись в дальнейший путь. От верховьев Илима недалеко до Лены. Перевалив через водораздел на лошадях, они вышли на берег Лены возле села Усть-Кут. Опять пересели в лодки и поплыли вниз по течению Лены до Якутска. В Якутск прибыли во второй половине июня 1726 года.
Осталась самая трудная часть пути. Реки между Леной и Охотским морем быстры, порожисты, малосудоходны и, главное, не сплетаются своими притоками так, как реки бескрайной сибирской равнины. От Якутска до Охотска не было в то время даже тропы — сплошная лиственничная и кедровая тайга, покрывающая сопки. А между тем отряд Беринга, проходя через Сибирь, сильно вырос — главным образом за счёт плотников и других мастеров, которые необходимы были для строительства корабля. Беринг нанимал их всюду, где только мог. Но особенно выросли грузы. К востоку от Лены нигде нельзя было достать никакого продовольствия, кроме, может быть, рыбы. В Якутске нужно было запастись мукой на несколько лет вперёд. Муки требовалось так много, что добыть её всю сразу оказалось невозможным. Нужно было найти выход из положения, и Беринг составил такой план.
Он разделил экспедицию на три отряда. Первый отряд должен был отправиться верхом на лошадях, захватив с собой большую часть заготовленной провизии и лёгкие вещи. Этот отряд возглавил сам Беринг. Второй отряд, захватив самые тяжёлые и громоздкие грузы, должен был на лодках попытаться пройти по рекам как можно ближе к Охотскому морю. Во главе второго отряда Беринг поставил Шпанберга. Третий отряд должен был зазимовать в Якутске, чтобы заготовить как можно больше продовольствия и весной 1727 года доставить это продовольствие в Охотск. Этот отряд, самый малочисленный, поручен был Чирикову.
Первый отряд двинулся из Якутска в конце августа на 663 лошадях. На каждую лошадь было навьючено пять пудов груза. Путь до Охотска был настолько тяжёл, что 267 лошадей пали по дороге. И всё же Беринг со своим отрядом был в Охотске уже в первой половине октября — через двадцать месяцев после отъезда из Петербурга.
Гораздо хуже обошлось дело с речным отрядом Шпанберга. Он двинулся в путь на тринадцати плоскодонных лодках. Лодки были плоскодонные, чтобы легче проходить в мелких местах, но это помогло мало, потому что они были тяжело нагружены и сидели глубоко. Поплыли сначала вниз по Лене — до впадения в Лену реки Алдан. Двинулись вверх по Алдану — до впадения в него Майи. Поплыли по Майе — до впадения Юдомы. Из всех рек Ленского бассейна Юдома ближе всех подходит к Охотскому морю. Шпанберг знал, что на берегу той излучины реки, откуда ближе всего к Охотску, поставлен большой деревянный крест. Этот опознавательный знак на Юдоме так и называли в то время — Юдомский крест. Нужно было во что бы то ни стало дойти до Юдомского креста, прежде чем Юдома замёрзнет. Сделать это Шпанбергу не удалось.
Лодка его вмёрзла в лёд за несколько сот километров от Юдомского креста. Случилось это уже в начале ноября. Что делать дальше? Зимовать здесь и тронуться в дальнейший путь следующим летом? Но ведь без этих грузов построить корабль невозможно. Застрянешь тут, и морское плаванье отложится на целый год. Шпанберг был деятелен и энергичен, допустить такой задержки он не мог. Он потребовал от якутов и тунгусов, живших по берегам Юдомы, чтобы они доставили ему собачьи упряжки и нарты. Заставить их он мог только силой, и он заставил их силой — кнутом и виселицей. Ему удалось собрать сто запряжек и нарт, и он перегрузил на них то, что было в лодках. Но и на ста нартах весь груз не поместился, и часть его пришлось оставить на берегу.
Начался чудовищный по трудности зимний переход, в самые морозы, через горы, леса и снежные пустыни. Вместе с нартами шли их владельцы — якуты и тунгусы, насильно мобилизованные Шпанбергом. Продовольствия не хватило, начался голод. «Идучи путём, — писал впоследствии Беринг в своём донесении, — оголодала вся команда, и от такого голоду ели лошадиное мёртвое мясо, сумы сыромятные и всякие сырые кожи, платье и обувь кожаные». Тунгусы разбегались, уводя своих собак, Шпанберг пытался их ловить, но они бесследно пропадали в тайге. Переход длился два месяца. К концу января 1727 года сорок нарт из ста добрались до Охотска. Недоставленные грузы с шестидесяти нарт, брошенные, валялись в снегу на всём протяжении пути.
А между тем в Охотске у Беринга создалось крайне трудное положение. Охотск, единственное тогда русское поселение на Охотском море, состоял в те времена всего из десяти изб. Пришедшие с Берингом люди не могли в них поместиться, и прежде всего нужно было строить жильё. Нужно было строить амбары для грузов. А тут оказалось, что лошадей, приведённых Берингом, совершенно нечем кормить, и они ежедневно десятками околевали от голода. Пользы от них не было никакой, и людям на себе приходилось таскать камни, брёвна, глину. И вот вдруг в середине зимы выяснилось, что Шпанберг растерял в пути большую часть грузов, необходимых для постройки корабля. Надо было немедленно спасать грузы. Беринг сразу же послал всех людей, способных двигаться, обратно на Юдому. Теперь уже не было и собак, и люди волочили нарты на себе. Дело это в февральские морозы оказалось до того мучительным и трудным, что многие умерли в пути. Разбегались теперь не только тунгусы, но и русские. Но Шпанберг наказывал непокорных с обычной своей жестокостью, и к апрелю большая часть грузов была уже в Охотске.
Теперь Берингу предстояло решить, что делать дальше. Откуда начать своё морское плаванье к северу? В инструкции Петра говорилось об этом довольно неопределённо: «Надлежит на Камчатке или другом тамож месте зделать два бота с палубами». Следовательно, Беринг, не нарушая инструкции, имел право построить свой корабль в Охотске и начать плаванье отсюда; обогнув Камчатку с юга, он мог двинуться на север, не прибегая к перегрузкам. Это было бы наиболее естественно и с точки зрения затраты труда и времени наиболее выгодно. Однако Беринг отверг этот план. Он остановился на другом: переправить грузы на восточное побережье Камчатки, там построить корабль и оттуда начать плаванье. Возможно, здесь сказалась присущая ему нелюбовь к слишком решительным поступкам. Кроме того, у него, видимо, было преувеличенное представление об опасности плаванья вокруг Камчатки. Но, скорее всего, егo соблазнил недостроенный шитик, который он обнаружил в Охотске. Этот шитик легко было достроить за несколько недель. На нём можно было пересечь Охотское море и добраться до Камчатки. Но, конечно, нечего было и думать плыть на нём по Тихому океану к Северу.
Шитики строили так: в основу клали выдолбленный древесный ствол, который назывался «трубой», или «днищем»; к нему нашивали боковые доски — отсюда и название «шитик». Получалось судно длиной метров в десять, шириной метра в четыре. Достроив найденный в Охотске шитик, Беринг назвал его «Фортуной». Он немедленно начал грузить «Фортуну», но, конечно, в ней не поместилась и половина грузов. Уже 30 июня «Фортуна» под командованием Шпанберга вышла в море и взяла курс к Камчатке, но не к восточному её побережью, а к ближайшему, западному, к устью реки Большой, впадающей в Охотское море.
Через несколько дней, 3 июля, в Охотск прибыл Чириков со своим отрядом. Переход в отличие от Шпанберга он совершил вполне благополучно и привёз из Якутска 2 300 пудов муки. Узнав о распоряжениях Беринга, он остался ими недоволен и не скрывал этого. Он считал, что если уж отказались от мысли строить большой корабль в Охотске, то нужно было попытаться переправить грузы прямо на восточный берег Камчатки. Но говорить об этом было поздно, потому что «Фортуна» уже ушла в море.