Pada 1594 ia meninggalkan Amsterdam dengan 2 kapal untuk mencari celah timur laut di utara Siberia menuju Asia Timur. Ia mencapai pesisir barat Novaya Zemlya, dan mengikutinya ke utara, akhirnya terpaksa kembali saat mendekati ujung utara.
Pada tahun berikutnya, ia memimpin ekspedisi lain 7 kapal, yang menuju selat antara pesisir Siberia dan Kepulauan Vaygach, tetapi ia terlambat menemukan perairan terbuka. Perjalanan ketiganya juga gagal dan mengakibatkan kematiannya. Saat itu ia memimpin 2 kapal, yang dikapteni oleh Jan Rijp dan Jacob van Heemskerk. Pada perjalanan keluar mereka melihat Kepulauan Beruang dan Svalbard (juga dikenal sebagai Spitsbergen), setiap kedua kapal itu terpisah. Kapal Barentsz, dikapteni oleh Heemskerk, terperangkap es setelah mengelilingi utara Novaya Zemlya, dan para kru terpaksa menghabiskan musim dingin di Novaya Zemlya, menghancurkan bangunan bagian atas kapal dan menggunakan kayunya untuk membangun pondok. Karena kapal itu tak bisa dibebaskan dari es awal 1597, rombongan Barentsz meninggalkannya dengan 2 perahu terbuka pada 13 Juni, dan sebagian besar kru pergi, diambil oleh kapal Jan Rijp di Semenanjung Kola dekat Murmansk.
Kisah musim dingin yang mengerikan yang dihabiskan di Novaya Zemlya diterbitkan sebagai buku harian Gerrit de Veer, tukang kayu kapal, yang merupakan orang pertama yang mengamati anomali atmosfer yang dikenal sebagai efek Novaya Zemlya.
Pada 1871, rumah di mana Barentsz dan krunya menghabiskan musim dingin ditemukan tak terganggu, dengan banyak relik, yang dipelihara di Den Haag; dan pada 1875, bagian perjalanan aslinya ditemukan.
