Die Engländer kamen nie weiter als bis Nowaja Semlja, während die holländischen Expeditionen des 16. Jahrhunderts bis zur Karasee gelangten, bevor sie vom Eis gestoppt wurden.
Willem Barentsz befand sich 1594 auf einer solchen Expedition. 1595 schließlich meinten die Holländer, die Nordostpassage gefunden zu haben, und schickten eine weitere Expedition mit Barentsz aus. Diese bestand aus mehreren Schiffen, schwer mit Waren für den Chinahandel beladen. Die Reise scheiterte jedoch.

Die holländischen Kaufleute gaben nicht auf, sondern rüsteten 1596 zu einer neuen Expedition, die Barentsz als Lotse begleitete. Diese Expedition sollte im Juni desselben Jahres Spitzbergen erreichen.
Nachdem man auf Spitzbergen an Land gegangen war, zog die Expedition weiter, bis das Schiff östlich von Nowaja Semlja im Eis eingeschlossen wurde und versank. Die Mannschaft war gezwungen zu überwintern, und im Jahr darauf brach man in zwei offenen Booten in südliche Richtung auf. Auf dieser Fahrt starb Willem Barentsz, während die überlebenden Expeditionsteilnehmer sich nach vielen Strapazen bis zur Halbinsel Kola durchschlagen konnten. Dort stießen sie auf ein holländisches Handelsschiff, das sie zurück in die Heimat brachte.
Willem Barentsz führte während der gesamten Reise geografische Messungen durch, und 1599 wurde unter seinem Namen eine Karte über die Polargebiete gedruckt.
Zwei der Teilnehmer an diesen drei Expeditionen haben jeweils ihre Reiseberichte herausgegeben. Jan Huyghens van Linschoten war bei den beiden ersten Fahrten dabei, während Gerrit de Veer an den beiden letzten teilgenommen hatte. Sein Bericht ist in Form eines Tagebuches abgefasst. Beide Bücher sind mit einem reichhaltigen Bildmaterial versehen. Bei van Linschoten findet man außerdem Karten und topographische Ansichten, die unter anderem die ersten uns bekannten Abbildungen des Nordkap und von Vardö zeigen.