«До декабря время проходило сравнительно сносно, но с 7 декабря наступили сильные холода; мороз не давал возможности дыму выходить через трубу, и мы едва не задохнулись в жилом помещении. В конце концов пришлось прекратить топку, и тогда в комнате сделалось сразу холодно; скоро стены и пол покрылись снегом и льдом; виноградное вино замерзло, и мы решили, что неминуемо должны замерзнуть. Не зная, какими средствами защититься от холода, мы собрались все вместе, полузамерзшие, и совещались о том, что предпринять. Кто-то предложил зажечь каменный уголь, который был принесен с судна. Вечером был разведен огонь, быстро согревший комнату. Чтобы сохранить тепло как можно дольше, мы заткнули дымовую трубу и заделали дверь. Ободренные теплом, впервые после долгих мук, улеглись спать почти в домашних условиях. Хорошо, что мы еще немного побеседовали. Внезапно некоторые из нас почувствовали головокружение и дурноту. Самые сильные поднялись со своих лежанок, с трудом открыли трубу и дверь. Но отворивший дверь тут же упал в обморок на снег; увидя это, я поспешил поднять его. Потом — принес уксус и тер ему лицо до тех пор, пока он не очнулся». Так о пребывании на зимовке рассказал в своем дневнике летописец экспедиции Виллема Баренца — Геррит Де–Фер.
После экспедиций Артура Пита и Чарльза Джекмена, которые в 1580 году по следам судов Виллоуби пришли к северным берегам Московии, инициатива в деле отыскания Северо–восточного пути перешла к Голландии, которая освободилась из-под власти испанцев. А вскоре — стала одной из сильнейших морских держав мира. Деятельность «Московской компании» постепенно ограничилась посылкой судов в Северную Двину.
Возможностью установить торговые сношения с Китаем и Индией Северо–восточным путем особенно заинтересовался голландский купец Балтазар Мушерон. Начиная с 1584 года, в течение почти 10 лет, он через своих агентов, находившихся в Московии, собирал сведения о Севере России и о Ледовитом океане. В 1593 году Мушерон сделал своему правительству доклад об установлении торговых сношений с Дальним Востоком по северному пути вокруг Евразии. Соблазненные заманчивой перспективой участвовать в выгодах непосредственной торговли с Индией и Китаем, которая все еще находилась в руках Испании и Португалии, голландцы не пожалели средств и снарядили в 1594 году арктическую экспедицию в составе четырех судов. Два из них — «Лебедь» под началом Корнелия Ная и «Меркурий» под началом Брандта Тетгалеса — должны были проникнуть в Карское море через один из проливов у Вайгача. Два других (еще один «Меркурий» и промысловая шхуна) под началом Виллема Баренца, по совету географа Петра Планциуса, должны были пробраться в Карское море вокруг северной оконечности Новой Земли, достичь Обской губы и оттуда подняться по реке Обь к столице Китая Кумбалик (Пекин). В те годы в Европе существовало странное представление, что Кумбалик расположен на озере, из которого вытекает река Обь.
4 июля Баренц достиг Новой Земли. На следующий день он миновал западный вход в пролив Маточкин Шар и достиг мыса Сухой Нос. Здесь, на берегу, голландцы обнаружили признаки пребывания человека. Следуя дальше на север, Баренц миновал остров, названный им Крестовым из-за того, что на мысу стояли 2 креста с русскими надписями. Позднее этот остров будет назван островом Пинегина. Продолжая двигаться на север, 13 июля Виллем Баренц почти достиг 78 градусов северной широты, но, встретив беспредельные льды, был вынужден повернуть к Новой Земле. 29 июля суда Виллема Баренца достигли безымянного мыса на Новой Земле.
Через пару дней неподалеку они случайно заметили группу небольших островов, где увидели более 200 «сильных морских чудовищ, размерами много превышающими быка». Вероятно, это было огромное стадо моржей. Вновь открытые острова Виллем Баренц назвал Оранскими островами. Однако с севера снова пришли льды, и голландским судам пришлось отступать на юг. В конце концов они достигли пролива Костин Шар и обнаружили, что здесь до них, приблизительно в 1584 году, побывал голландец Оливер Брюнель. В августе 1594 года к югу от залива, названного Варенцом заливом Святого Лаврентия (возможно, губа Строганова) голландцы обнаружили корпус покинутого русского судна, развалины трех домов, несколько кулей ржаной муки и несколько могил. Кто были эти несчастные мореходы, и сегодня установить не удалось. Спускаясь далее к югу, у острова Долгий 15 августа Виллем Баренц встретил ходившие южным путем экспедиционные суда «Лебедь» и «Меркурий». Оба арктических отряда собрали ценные сведения по картографии островов Северного Ледовитого океана и об их природе. Вернувшись домой, голландские мореплаватели рассказали о том, что через Югорский Шар можно выйти в открытое (Карское) море. Многим тогда казалось, что вопрос о возможности прохода Северо–восточным проходом в Китай и Индию уже разрешен, а потому была немедленно организована новая экспедиция, которая должна была начать торговые сношения по вновь открытому пути вокруг северной Татарии.