In 1596 vertrok Willem Barentsz met zijn bemanning voor de derde keer naar het noorden, opnieuw met Jacob van Heemskerk. Dit keer voer Barentsz vanaf Scandinavië niet oostwaarts, maar noordwaarts. Hij ontdekte een eiland dat hij Veere eiland noemde (het tegenwoordige Bereneiland) en verder noordelijk, een land dat hij Het Nieuwe Land noemde (het huidige Spitsbergen). Terug op Bereneiland, werd de expeditie gesplitst. Een schip, onder bewind van Jan Corneliszoon Rijp, probeerde westelijk van Spitsbergen een doorvaart te vinden. Barentsz onderzocht de zeeën tussen Spitsbergen en Nova Zembla. Barentsz slaagde er inderdaad in de noordpunt van Nova Zembla te ronden, maar kwam daarna vast te zitten in het ijs. Van aangespoeld drijfhout werd een huis gebouwd, dat bekend staat als Het Behouden Huys, waarin vervolgens de winter werd doorgebracht. Gerrit de Veer maakte van deze onderneming een reisverslag.