No verão de [[1594]] Barents saiu de [[AmsterdãoAmesterdão]] ao comando de dois navios com o objectivo de encontrar a então inexplorada [[Passagem do Nordeste]] que, pelo norte dos continentes europeu e asiático, permitisse atingir a [[China]] e o [[Japão]]. Navegou para norte, ao longo da costa norueguesa, contornou a península da [[Escandinávia]] e atingiu a costa ocidental da ilha de [[Nova Zembla]], que tentou contornar pelo norte. O surgimento do inverno e as latitudes elevadas do norte da ilha, cujo extremo quase atingiu, não permitiram a continuação da viagem, sendo a expedição obrigada a regressar<ref name="godutch">{{citar web |url=http://www.godutch.com/windmill/newsItem.asp?id=257 |título=Historic expedition led by Willem Barentsz nears 400th anniversary |acessodata=20 de junho de 2012 |autor= |coautores= |data= |ano= |mes= |formato= |obra= |publicado= |páginas= |língua= |língua2= |língua3= |lang= |citação= }}</ref>.
No ano seguinte (1595), Barents comandou nova expedição, desta vez incluindo sete navios, numa nova tentativa de encontrar a Passagem do Nordeste. Tendo em conta a experiência do ano anterior, tentou contornar [[Nova Zembla]] pelo sul, através do estreito entre a costa siberiana e a ilha de [[Vaygach]], mas chegou demasiado tarde para encontrar águas livres de gelo, sendo obrigado a retornar sem ultrapassar aquela ilha<ref name="godutch"/>.
