21 июля 1878 года полностью снаряженная и готовая к дальнейшему плаванию "Вега" покинула шведский порт Гётеборг. Пароход шел в сопровождении трех судов, приобретенных в Швеции Сибиряковым и предназначенных для плавания по сибирским рекам - Енисею и Лене.
Корабли без каких-либо приключений пересекли Баренцево море, подошли к Новой Земле и через пролив Югорский Шар проникли в Карское море, которое оказалось свободным ото льда на всем их пути до Енисейского залива.
Погода была теплой, и над морем висела пелена тумана. Пришлось дожидаться, пока туман рассеется, чтобы войти в бухту острова Диксон.
После непродолжительного перерыва флотилия двинулась дальше на восток. В ее составе оставалось лишь два судна - "Вега" и небольшой пароход "Лена", предназначенный для плавания по одноименной реке. Два других корабля - пароход "Фразер" и парусник "Экспресс"- остались в бухте острова Диксон, ибо их маршрут лежал вверх по Енисею. Им предстояло доставить торговые грузы в южную, заселенную часть Сибири.
Едва остров Диксон скрылся вдали, появились плавучие льдины, хотя и разрозненные, но, тем не менее, представлявшие значительную опасность для кораблей, которым приходилось лавировать между ними чуть ли не на ощупь из-за непрерывных туманов. Флотилия медленно продвигалась на восток, часто делая вынужденные остановки.
Вот уже остался позади мыс Челюскин на полуострове Таймыр, самая северная оконечность Азиатского материка. Отсюда Норденшельд решил следовать к Новосибирским островам напрямик, а не вдоль побережья, как они следовали прежде. Некоторое время суда шли строго на восток, но льды и густые туманы вынудили мореплавателей изменить курс и вновь приблизиться к берегу в поисках чистой воды.
В последних числах августа, обменявшись прощальными гудками, пароходы расстались: "Вега" продолжила плавание на восток, "Лена" же повернула на юг, к дельте реки Лены, проход в которую ей еще предстояло отыскать.
Между тем с каждым днем плавание становилось все более трудным. Льды то обступали корабль со всех сторон, то вдруг расходились, давая ему проход. Чтобы пробиться сквозь льды, нередко приходилось пускать в ход топоры и ледорубы.
Был уже конец сентября. Мороз все усиливался. С трудом преодолевая сопротивление льдов, "Вега" подошла к Колючинской губе.
Незадолго до этого произошла первая встреча мореплавателей с чукчами (6 сентября), как раз в то время, когда корабль огибал мыс Шелагский. "Вдалеке показались две лодки из кожи, - вспоминал впоследствии Норденшельд, - они были набиты смеющимися и болтающими туземцами - мужчинами, женщинами, детьми, криками и жестами выражавшими желание посетить нас. Машину остановили, лодки причалили, и множество одетых в меха существ с обнаженными головами полезли по трапу на палубу. Было ясно, что они уже прежде видели суда. Начался оживленный "обмен речами", но скоро оказалось, что ни у нас, ни у туземцев нет никакого общего языка. Это было неприятное обстоятельство, но хозяева и гости усердно помогали себе знаками. Сами они себя называли "чукч", или "чаучу".
В ожидании появления благоприятных условий для дальнейшего движения сквозь льды "Вега" укрылась в небольшой бухте, на берегу которой находилось стойбище чукчей.
Шесть дней, проведенные здесь, хотя и обогатили знания путешественников об особенностях жизни и быта местных жителей, но, по всей вероятности, сыграли роковую роль: эта задержка привела к неизбежности зимовки, хотя от Колючинской губы до Берингова пролива было совсем недалеко - около двухсот километров. "Веге" так и не удалось освободиться от ледового плена, в который она попала внезапно, когда никто этого не ожидал. Девять месяцев провели мореплаватели на неподвижном судне, вмерзшем в лед всего в полутора километрах от берега. Их часто навещали чукчи, с которыми сложились самые доброжелательные отношения.
Как-то в начале зимовки, когда Норденшельд стоял на палубе судна вместе с капитаном и зоологом Нордквистом, обсуждая с ними вопросы организации быта экипажа корабля на весь срок вынужденной стоянки, он обратил внимание на то, что зоолог рассеян, то и дело отворачивается от собеседников и что-то разглядывает в направлении берега.
- Послушайте, Нордквист, - тоном, в котором сквозило некоторое недовольство, сказал Норденшельд, - согласитесь, что не слишком вежливо крутить головой вправо и влево, когда с вами говорят, делая при этом вид, будто вы занимаетесь крайне важным делом.
- Ах, прошу прощения, господин Норденшельд, - ответил извиняющимся тоном зоолог, - право, я не хотел этого. Но взгляните, - он протянул руку и указал на группу людей, приближающуюся к судну по льду, - не кажется ли вам, что они тащат на нартах больного человека?
Норденшельд схватил бинокль и несколько мгновений пристально всматривался в медленно двигающуюся кучку чукчей.
- Похоже, вы правы, Нордквист, - наконец отрывисто произнес он, - лежащий на нартах человек совершенно недвижим. Видимо, он без сознания. Паландер, - обратился он к капитану, - распорядитесь, чтобы вызвали врача.