巴倫支探險隊凱旋後，荷蘭政府立即組織第二支探險隊。探險隊擴大到7艘船，滿載各種貨物，攜帶了一年半的給養。納伊當上了船隊指揮，捷特卡列斯任副指揮，巴倫支任船隊主舵手（類似艦隊參謀長）和一艘船的船長，林斯考登作為商務代表再次隨同出航。這是探尋東北航路以來西方派往北極海區的一支最大的艦隊。
1595年8月，船隊繞過挪威最北部的諾爾辰角（Northern，亦為北角，在北角以東）後分開航進。一支分隊向東南進入白海；另一支分隊向東航行。向東的分隊在北緯70度半的緯線上還未走到新地島就遇到許多巨大的浮冰。船隊隻得轉向南邊尤戈爾海峽，然而尤戈爾海峽也快被冰封住了。9月初，分隊才穿過海峽進入喀拉海，但很快又被冰塊阻擋住。巴倫支對納伊和捷特卡列斯行動不果敢，遇到險阻就畏葸不前公開提出了批評。
船隊在一個小島停靠，水手們登上了小島。兩個船員遭熊襲擊身亡。這恐怕是地理大發現以來首次探險者被野獸所害的例子。在小島上召開了軍官會議，除巴倫支一人反對外，大家一致決定返航。1595年12月，探險隊回到荷蘭，沒有取得任何發現成果。
第二次探險無果而回後，荷蘭當局不再以國帑組織探險隊，而改為設立高額獎金，以獎勵任何發現打通東北航路的單位或個人。獎金金額高達25000金佛洛林。這項措施激發了阿姆斯特丹市議會的積極性。市議會出資裝備了兩艘船，任命黑姆斯克爾克和楊·魯普為船長，巴倫支誌願在黑姆斯克爾克船上當領航員。船員們大都是單身漢，以免牽掛妻兒。
新的探險隊認為，1595年的探險之所以失利，其原因在於啟程的時節太晚。於是他們決定提前兩個月於5月出發。在航行過程中，巴倫支很快與魯普和黑姆斯克爾克發生爭執。巴倫支主張走東北航線先到新地島。而魯普執意往北航行。他天真地以為北極海域不會封凍。黑姆斯克爾克支持魯普。於是船隊按魯普設計航線北上。1596年6月9日，他們在北緯74度半海麵上發現一個海島，船員們在島上見到一隻死去的白熊，便把它取名為熊島（今屬挪威）。他們在熊島停留4天後向北偏西方向航進。6月19日，荷蘭人在北緯80度處再次發現一片陸地。他們以為這是格陵蘭島的一部分。其實這是西斯匹次卑爾根島的西海岸。魯普說：“……我們之所以把這片陸地稱作斯匹次卑爾根，是因為這塊陸地有許多高峭的山峰。”該地名由荷蘭語spits（點）和bergen（山）組成，意為尖峭的山地。船隊的醫生德·菲爾寫道：“……盡管我們認為這裏是格陵蘭，盡管它位於北緯80度或更北一點，但這塊陸地上有豐茂的綠草，可以飼養各種食草動物……。”他們還發現許多野鵝在崖岩上築窩孵化，從而糾正了野鵝在樹上築窩棲息的錯誤觀念。他們在斯島西北海岸探察了好幾天，最後被不可逾越的冰層擋住，不得不原路折向南方。7月1日，他們再次來到熊島。此間，巴倫支與魯普又發生了分歧。魯普主張再從斯匹次卑爾根出發，發現它的東海岸，尋找通向北極的無冰航道，進入不封凍的暖水域，然後直奔東亞。魯普一再主張往北穿越北極的地理學理論在於，當時一些人認為，南極、北極地區比中緯度地、赤道地要冷，據說是因為兩極地比中低緯度地離太陽遠（實際應為太傾斜）。但高山頂卻比山腰山腳更冷，而高山頂不是更接近太陽嗎？所以穿過冰層後極地也許還會暖和一些。巴倫支則認為，去中國的東北航路隻應向東去探尋。這次黑姆斯克爾克讚成巴倫支的意見，於是兩船分開，各奔征程。
巴倫支、黑姆斯克爾克徑直向東航行。7月17日，他們在北緯73.5度左右靠近了新地島，然後向北航行。途中他們與浮冰做了反複的鬥爭，8月19日到達新地島北島最北部偏東南的希望角。他們繞過了新地島最北部並向東南海岸前進了一小段，但浮冰和冰層阻止了他們前進。8月21日，他們不得不停泊在新地島北部偏東南的一個港灣，他們稱為冰港。當晚港灣就封凍了，船舶被凍在冰裏，他們隻得在這裏越冬。他們就地取材修建了能防嚴寒和野獸的越冬住所營地。這是文明人類在如此之北的北極地區的第一個越冬營地和第一次越冬。探險者們盡量把生活安排得好一些，還堅持洗熱水澡、做遊戲、體育鍛煉、開音樂會。11月，北極的極夜來臨，三個月中不見太陽，整天的光線隻相當於天快黑盡時。氣溫降到攝氏零下60度。隊員們主要靠獵捕熊、狐和喝融雪水維持。壞血病也逐步襲來，大多數得了壞血病。開春以前，17人中已死了2人。5月裏，冰層開始鬆動，但冰中的大船已損壞並無法修複。荷蘭人拆下大船的木料造了兩隻帶帆的小敞船。1597年6月中旬，荷蘭人開始原路返航。波濤洶湧，浮冰不斷，航行困難。兩隻小船經過6天的拚搏才繞過他們所稱的“冰角”。在冰角之外的海上，1597年6月20日，因壞血病而已入膏肓的一個水手和巴倫支相繼死去。德·菲爾寫道：“威廉·巴倫支的逝世給我們帶來了極大的痛苦，我們每個人都悲痛欲絕。因為他是我們的主要領導人，同時又是我們必不可少的領航員、朋友和同伴。”他的遺體按慣例葬人大海。從19世紀中葉起，他反複航行過並航遍了各個海區的巴倫支海被命名如斯，以資紀念，他參與發現的斯匹次卑爾根群島東部的一個小島也被稱為巴倫支島。1871年，挪威獵海象人發現了巴倫支一行在新地島北岸東南處的越冬營地小屋和越冬者留下的一些東西。5年以後，人們才在已倒塌的小屋廢墟裏找到巴倫支寫的關於那次航行和越冬情況的報告。報告“說明我們怎樣離開荷蘭駛往中華王國，在這片陸地上我們發生了什麼事”。1980年，蘇聯探險者又發現了巴倫支他們遺棄的船舶殘骸。