Initiativet til å finne sjøveien til Cathai kom fra den mektige handelsmannen Balthasar de Moucheron i den nederlandske provinsen Zeeland. Han drev det stort i handel med Russland, med Arkhangelsk som knutepunkt. Myndighetene i Holland og Zeeland tok på seg kostnadene. de Moucheron hadde også støtte fra tidas beste fagfolk, slik som forfatteren og navigatøren Jan Huygen van Linschoten og geografen Petrus Plancius.
Men hvor skulle man legge kursen? Her var det uenighet mellom Barentsz og Cornelis Nay, som hadde kommando over to skip hver. Barentsz fulgte geografen Plancius og ventet dermed å finne nordøstpassasjen i et åpent hav nord for Novaja Semlja. Cornelis Nay og van Linschoten ville gå sør for Novaja Semlja – gjennom Jugorstredet (”Vajgatsjstredet”) og inn i Karahavet (”Det tartariske hav”).
Willem Barentsz' kart over Novaja Semlja, publisert av Gerrit de Veer. "Het behouden Huys" er stedet der Barentsz og mennene hans overvintret 1596-97. Det såkalte Vajgatsjstredet finner du mellom Novaja Semlja og fastlandet.
Denne flotte illustrasjon er fra en tysk utgave av Gerrit de Veers beretning om de tre ekspedisjonene til Barentsz. Bildet viser både nederlendernes og de innfødte nenetsernes virksomhet under den andre ekspedisjonen i 1595