За англичанами на поиски Северо-Восточного прохода двинулись голландцы. В июне 1594 г. из Голландии на север вышла экспедиция на трех кораблях и яхте с заданием открыть удобный морской путь в царства Катайское и Синское, проходящий к северу от Норвегии, Московии и Татарии. Одним кораблем командовал амстердамец Биллем Барентсзон (сын Барента), прославившийся под обычным у голландцев сокращенным отчеством Баренц — фамилии у него, как у человека простого происхождения, не было; второе судно шло под командованием Корнелиса Корнелисзона Ная, третье — Бранта Исбрантзона Тетгалеса. Торговым комиссаром на его корабле был Ян Хейген Линсхотен; он владел пером и описал это и последующее путешествия.

Близ устья Колы экспедиция разделилась: Най и Тетгалес двинулись прямо на восток, через Югорский Шар проникли в Карское море и достигли западного берега Ямала у 71 с. ш. Они считали, что открыли уже достаточно и что пора возвращаться, тем более что им было поручено только отыскать удобный путь.... Баренц повел свой корабль и яхту на северо-восток, с тем чтобы обогнуть с севера Новую Землю, за которой рассчитывал найти свободное ото льда море. 4 июля он увидел мыс, видимо Сухой Нос, западный мыс Северного острова (73 끇' с. ш., 53 45' в. д.). Продвигаясь на север, Баренц открыл о. Адмиралтейства (вторично после русских) и прошел пролив, отделяющий его от Новой Земли. На 75 54' с. ш. у острова голландцы нашли обломок русского корабля, а за 76 с. ш. миновали голый Остров с крестами — так назвал его Баренц, увидевший там два креста; несомненно, их поставили русские на могилах или как опознавательные знаки. Вот как далеко на север заходили русские зверобои уже в XVI в. В этом районе голландцы впервые увидели лежбища моржей и встретили белого медведя. С 13 июля продвижение на север очень замедлилось.

29 июля Баренц открыл у 77 с. ш. крайний северный мыс Новой Земли, названный Ледяным (мыс Карлсена), а 1 августа близ него - небольшие Оранские о-ва. ...Моряки не желали идти дальше. Поэтому... он счел за лучшее... вернуться к другим кораблям, взяв курс к Вайгачу... У Матвеева острова (69뀨' с. ш.) флотилия соединилась. Баренц был удручен поражением, капитаны Най и Тетгалес ликовали.

В сентябре все суда вернулись в Голландию. Два победителя были встречены с триумфом и возглавили в 1595 г. большую экспедицию. Баренц в ней был главным штурманом и капитаном одного из кораблей. Голландцы вернулись на родину, ничего не добившись.