Голландские купцы работали на два фронта. Одну экспедицию отправили на юг: корабли должны были добраться до Восточной Азин, обогнув Африку. Для этого девять амстердамских купцов объединили свои средства со средствами других заимодавцев и снарядили четыре корабля, которые мимо мыса Доброй Надежды поплыли в Индию. Одновременно была предпринята попытка найти северный путь, чтобы получить возможность плавать в Азию менее нездоровым маршрутом и не сталкиваясь с испанцами и португальцами. Таким образом, летом 1594 г. экспедиция из трех кораблей и одной рыбачьей яхты отправилась на север. Экспедицией руководил Виллем Баренц ван дер Схеллинг, опытный мореплаватель лет сорока от роду, пользовавшийся хорошей репутацией после того, как создал атлас Средиземного моря. Он был в первую очередь путешественником-исследователем, стремившимся открывать и наносить на карту новые территории. Во время этой экспедиции он создал карту западного побережья Новой Земли.
Его попытка найти путь на восток через север, двигаясь вдоль побережья Новой Земли, не удалась из-за пакового льда, но капитан другого корабля этой же флотилии, Корнелис Най, достиг определенного успеха: он смог провести свой корабль через пролив Вайгач в Карское море и думал, что проложил тем самым северный путь в Азию. Дальше они не пошли, так как спешили своевременно, до морозов, вернуться домой. Прерванную таким образом экспедицию решили продолжить на следующий год.
Следующая экспедиция преследовала уже не только исследовательские цели: на борт был взят также товар. Было снаряжено семь кораблей, из Зеландии, Энкхёйзена, Роттердама и Амстердама, чтобы начать торговлю с Восточной Азией.
Возглавлял экспедицию опять Виллем Баренц, но теперь рядом с ним стоял Якоб ван Хеймскерк, сравнительно молодой человек (ему было около тридцати лет), сын амстердамского парусных дел мастера, известный своим спокойным нравом и дипломатически ми способностями: в его обязанности входило ведение торговли. В дальнейшем, после экспедиций по полярным морям, он весьма успешно плавал в Азию южным путем. В 1607 г., будучи уже адмиралом Нидерландского флота, он погиб в битве при Гибралтаре. Его могила находится в Старой церкви в Амстердаме.
Корнелис Най также участвовал и в этой второй экспедиции, равно как и его товарищ по предыдущей экспедиции Ян Хёйген ван Линсхотен (1563-1611). Ян Хёйген ван Линсхотен был опытным моряком, который уже в 16 лет следом за старшими братьями поехал в Севилью, чтобы там наняться на испанский корабль и плавать в дальние края. Хотя Нидерланды в ту пору уже подняли восстание, они все еще входили в состав испанской империи, так что голландцы считались испанскими подданными. Ван Линсхотен прожил пять лет на Гоа, где работал чиновником; все эти годы он переписывал всевозможные документы, содержащие сведения об организации испанской и португальской торговли в Восточной Азии. Вернувшись потом в Нидерланды, он тотчас опубликовал эти секретные стратегические сведения. На основе добытой им информации Нидерланды в том же 1595 г. снарядили экспедицию в Азию по южным морям. Линсхотен мог бы присоединиться и к этой экспедиции, однако он уже обещал участвовать в плавании на север. Позднее, уже после выхода в свет описания зимовки Баренца на Новой Земле во время третьей экспедиции, Линсхотен также издаст свое описание первых двух плаваний.
Вторая экспедиция была затерта паковым льдом, так что немножко поторговать удалось только с местным населением, которое тогда называлось «самоедами». Да и в других отношениях эта экспедиция была неудачной: в драматический момент среди моряков вспыхнул мятеж, несколько человек было разорвано белыми медведями.
Тем не менее наследующее лето была предпринята еще одна попытка найти северный путь. Планциус считал, что если забрать севернее, чем это делалось до сих пор, то дрейфующего льда встретится меньше. Ему удалось убедить в этом Виллема
Баренца и нескольких амстердамских купцов, так что купцы на свои деньги снарядили два корабля, одним из которых командовали Виллем Баренц и Якоб ван Хеймскерк. Следуя новым маршрутом, они открыли по пути Медвежий остров и Шпицберген. Второй корабль, которым командовал Ян Корнелис Рейп, пытался найти проход вдоль западного побережья Шпицбергена, но безуспешно, и потому вернулся в Амстердам. Виллем Баренц обошел Новую Землю с севера, но его корабль все равно был затерт льдами, так что пришлось устроить зимовку на этом далеком северном острове.
Зима была очень суровой, моряки несколько месяцев провели в темноте полярной ночи, не все смогли в таких условиях выжить. В итоге в Амстердам вернулись двенадцать из семнадцати человек.
Зимовка на Новой Земле стала легендарной благодаря изданию подробного отчета о путешествии, написанного молодым корабельным плотником Херритом де Вейром, родственником ван Хеймскерка, участвовавшим также и в предыдущей экспедиции на Север. Этот отчет должен был служить оправданием команде, потерявшей корабль и товар. Выйдя в свет в мае 1598 г., отчет тотчас стал настоящим бестселлером. Его немедленно перевели на немецкий язык, затем последовало два переиздания, в 1599 и 1605 г. Впрочем, кое-кто относился к рассказу де Вейра скептически, так как не существовало никаких доказательств его правдивости. Такие доказательства были найдены лишь в XIX веке.