Правительство Нидерландов назначило большую премию тому, кто откроет Северо-Восточный проход, и амстердамский сенат снарядил два корабля, командирами которых были назначены Якоб Гемскерк и Ян Рейп. Баренц согласился пойти штурманом с Гемскерком. Считая, что неудача 1595 г. объясняется поздним выходом из Голландии, экспедиция двинулась в путь весной 1596 г. Рейп, вопреки мнению Баренца, настоял на северном направлении, чтобы войти в Полярное море, якобы свободное ото льдов. Неожиданно под 74뀦' с. ш. открылся остров, у которого был убит белый медведь, поэтому его назвали Медвежьим. Пробыв там четыре дня, голландцы пошли дальше, причем Рейп, видимо, зная о плавании русских к Груманту (Шпицбергену), взял курс на север, с уклоном к востоку. 19 июля близ 80 с. ш. голландцы увидели землю, принятую ими за часть Гренландии, с множеством заостренных вершин, поэтому назвали ее Spitsbergen.

Продвинувшись вдоль нее на запад, моряки обнаружили меридиональный залив — это был Вуд-фьорд на северном побережье о. Западный Шпицберген (у 14 в. д.). Через три дня, после неудачной попытки пробиться сквозь льды на северо- запад, голландцы повернули к югу и за 79 с. ш. нашли, по Де Феру, залив или пролив. Не дойдя лишь 15 км до южного выхода из этого, как мы теперь знаем, пролива Форлансуннет (длина 90 км), отделяющего Западный Шпицберген от о. Земля Принца Карла, они вернулись к северному выходу. 28 июня, обогнув мыс Фуглехукен (Птичий), моряки проследили весь западный берег Земли Принца Карла и почти весь юго-западный берег Шпицбергена.

1 июля корабли вернулись к Медвежьему острову. Здесь снова начались разногласия. Баренц настаивал на поисках прохода к востоку от Шпицбергена.

Гемскерк на этот раз присоединился к мнению Баренца, и корабли разделились. Рейп повел свое судно снова на север, Гемскерк и Баренц двинулись прямо на восток и 17 июля подошли к Новой Земле у 73o 20' с. ш., а затем повернули на север. В непрерывной борьбе со льдами они достигли 19 августа мыса Желания, а немного юго-восточнее — мыса Флиссингского (название дано Баренцем). Продвинуться дальше голландцы не смогли, вернулись к северному берегу и 26 августа остановились на зимовку в Ледяной Гавани.