Голландцы перехватили у англичан эстафету поиска северо-восточного прохода. Они еще в 60-х годах XVI века торговали с поморами и на Белом море, и на Печоре, и на мурманском берегу. В 1570 году голландец Симон ван Салинген впервые провел на Мурмане гидрографические исследования: измерял глубины, направление и скорость течений, координаты. Это было сделано за 160 лет до того, как была проведена съемка берега лейтенантом Винковым — в 1741 году.
В то время как Московская компания англичан смирилась с неудачами и все свои усилия направила на развитие торговых отношений с поморами Белого моря, посылая каждый год корабли в устье Северной Двины, голландцы совершили прорыв на восток. Особенно преуспел Оливер Брюнель, поступивший на службу к купцам Строгановым. Живя в Холмогорах, он изучил русский язык, а затем Строгановы отправили его на Обь (через Урал по рекам, а затем и морем — из устья Печоры). Совершив это плавание, Брюнель стал первым западным европейцем, прошедшим участок северного морского пути до Обской губы. Это произошло где-то около 1580 г. Потом он ездил в Европу и встретился с великим картографом Герардом Меркатором, которому сказал, что из устья Оби «можно достичь Китая в одно лето». Он попытался это сделать около 1584 года, организовав собственную экспедицию, но не смог из-за льдов пройти даже в Карское море.
Изыскания Брюнеля продолжил голландский купец Балтазар Мушерон. Он долго готовился, собирая на протяжении десяти лет сведения о русском севере. На его средства (и других привлеченных им купцов) и была организована первая экспедиция Виллема Баренца.
Новая Земля — двойной остров, или полуостров (еще было неизвестно), — вставал как досадное препятствие на пути искателей северо-восточного пути в Индию. Первым попытался обогнуть его с севера голландский мореплаватель Виллем Баренц. В 1594 году четыре голландских судна, одним из которых, под названием «Меркурий», командовал Баренц, вышли в поход. На подступах к Новой Земле разделились: три судна пошли в пролив Югорский Шар, а Баренц — на север, параллельно новоземельскому берегу. Проплывая на корабле «Меркурий» вдоль берега Новой Земли, обнаружили следы пребывания русских. Кресты над могилами на одном из прибрежных островов побудили Баренца назвать этот остров Крестовым. Потом он встретит покинутое селение: три деревянных дома, корпус судна, много пустых бочек, мешки со ржаной мукой и несколько могил. У него не было сомнений в том, что русские давно осваивают эти острова.
Баренц взял курс прямо на север, потому что надеялся найти там свободное ото льдов море. Но льды остановили судно на широте 73°21', и Баренц вынужден был повернуть к Новой Земле. Так он оказался у ее северной оконечности, где открыл небольшую группу островов, занятых огромным лежбищем моржей, назвав их Оранскими. Дальше на север «Меркурий» не пустили льды. Баренц возвращается и встречается с остальными кораблями экспедиции, капитаны которых, Корнелий Най и Брандт Тергалес, провели их через пролив Югорский Шар в Карское море.
Те же три капитана, включая Баренца, отправились в следующем году в новую экспедицию на северо-восток, погрузив на шесть судов всевозможные товары. Голландцы были уверены в том, что проход в Карское море найден и дойти до Китая удастся. Но на сей раз их ждало разочарование: хотя они и прошли через Югорский Шар, но море заполнил сплошной массив льда, преодолеть который было невозможно. На совещании капитанов 15 сентября 1595 года было принято и зафиксировано следующее решение: «Мы, нижеподписавшиеся, объявляем перед Богом и миром, что мы сделали, что от нас зависело, чтобы проникнуть через Северное море в Китай и Японию, как нам приказано в наших инструкциях. Наконец, мы увидели, что Богу не угодно, чтобы мы продолжали наш путь и что надобно отказаться от предприятия».
Баренц был единственным, кто возражал против этого капитулянтского решения и предлагал продолжить попытку, испробовав северный путь, уже разведанный им в прошлом году. Но он подчинился мнению большинства, и вся экспедиция вернулась в Голландию.
Купцы и правительство не могли смириться с неудачей. Назначена премия тому, кто сумеет пройти северным путем в Китай, и организована новая экспедиция — из двух судов, под командой Ян ван Рийпа и Якова ван Гемскерка. Баренц согласился принять участие в плавании в качестве старшего штурмана на одном из кораблей, хотя он был, несомненно, «душой» экспедиции.
10 мая 1596 года суда вышли из Амстердама. В этом плавании был открыт Шпицберген, принятый голландцами за часть Гренландии. Мимо него не удалось пройти на север, и Баренц, оставив ван Рийпа у открытой земли, направился к Новой Земле, продолжая верить, что именно она откроет ему северо-восточный проход. Очень странно представлял он себе путь в Китай: достаточно было, обогнув Новую Землю, войти затем в Обскую губу, подняться по реке Оби к озеру, из которого она вытекает, а на озере и находится столица Китая Кумбалик (так европейцы называли тогда Пекин).
И вот голландцы снова у Крестового острова, на берег которого высаживаются, чтобы осмотреть русские кресты. Пока вырезали они на них свои надписи, остров окружили льды: пришлось задержаться на несколько дней. «Мы воспользовались этой стоянкой, — как пишет Геррит де Фер, летописец экспедиции, — чтобы выстирать на берегу наши рубашки и выбелить их на солнце». Когда льды отнесло течением, двинулись дальше вдоль западного берега. Дошли до северной оконечности Новой Земли. Ее Баренц назвал мысом Желания — уж очень сильно желал он, чтобы за мысом этим открылся безлюдный морской простор. Но этого не произошло — одни льды расстилались до самого горизонта.
21 августа 1596 года, спасаясь от напора льдов, голландцы вошли в небольшую бухту на северо-восточном берегу архипелага. В этой бухте, названной Баренцем Ледяной Гаванью, остались на зимовку. Это была первая зимовка европейцев в столь высоких арктических широтах. Прошла она очень тяжело. Первой жертвой пал корабль, затонувший 30 августа. Пришлось собирать плавник на берегу и строить из него зимовочный дом. Он оказался плохо приспособленным для суровой зимы. Голландцы почему-то не воспользовались опытом русских, умевших строить небольшие, но теплые избы с обязательными сенями и печкой-каменкой. Сколоченный наскоро из сырого материала — плавника, слишком просторный, если судить по рисунку де Фера, их дом совсем не сохранял тепло.
Вот что записывал он в своем дневнике: «Погода жестокая и дует очень холодный и почти невыносимый ветер с востока. Мы с жалостью смотрим друг на друга, опасаясь, что мы погибнем, если мороз еще усилится… Какой большой огонь мы ни раскладываем, согреться не можем… Стоишь возле огня, так близко к нему, что чуть не обжигаешь ноги спереди, а спина мерзнет и покрывается инеем».
Уже в самом начале зимовки стали иссякать продовольственные запасы. И только охота на белых медведей, часто подходивших к дому, да ловля песцов капканами, спасали от голода. И все же неумолимая цинга посетила зимовку. Болели многие, но особенно тяжелым состояние было у Баренца. Когда 14 июля 1597 года, отремонтировав шлюпку, голландцы вышли из Ледяной Гавани в море, никто и подумать не мог о том, что Баренц умрет первым. Между тем это случилось меньше чем через неделю после начала плавания. Он успел написать краткий отчет о плавании и оставил его в дымовом отверстии дома, вложив в роговую пороховницу. Потом во время плавания следил по карте за продвижением шлюпки. Следом за ним умер матрос Андиссон.
А шлюпка достигла юго-западной оконечности Новой Земли и у острова Междушарского произошла встреча с двумя русскими лодьями. Поморы поделились хлебом с голландцами и доставили их в Колу, где стоял корабль Рийпа, успевший совершить торговый рейс к русским.
В 1608 году в поиск северо-восточного прохода включился знаменитый тогда Генри Гудзон, только что (в 1607 году) поставивший рекорд плавания на север: он достиг в районе Шпицбергена 80°23' с.ш. Отправившись на восток, Гудзон дошел до западного берега Новой Земли, высадился на берег немного южнее пролива Маточкин Шар и нашел, что «для человеческого взора это приятная земля». Тогда он произвел самые первые в Арктике наблюдения над наклонением магнитной стрелки.