За англичанами на поиски Северо-Восточного прохода двинулись голландцы. В июне 1594 г. из Голландии на север вышла экспедиция на трех кораблях и яхте с заданием «открыть удобный морской путь в царства Катайское и Синское, проходящий к северу от Норвегии, Московии и Татарии».
Одним кораблем командовал амстердамец Биллем Барентсзон (сын Барента), прославившийся под обычным у голландцев сокращенным отчеством Баренц — фамилии у него, как у человека простого происхождения, не было; второе судно шло под командованием Корнелиса Корнелисзона Ная, третье — Бранта Исбрантзона Тетгалеса. Торговым комиссаром на его корабле был Ян Хейген Линсхотен; он владел пером и описал это и последующее путешествия.
Близ устья Колы экспедиция разделилась: Най и Тетгалес двинулись прямо на восток, через Югорский Шар проникли в Карское море и достигли западного берега Ямала у 71° с. ш. «Они считали, что открыли уже достаточно и что пора возвращаться, тем более что им было поручено только отыскать удобный путь...». Баренц повел свой корабль и яхту на северо-восток, с тем чтобы обогнуть с севера Новую Землю, за которой рассчитывал найти свободное ото льда море. 4 июля он увидел мыс, видимо Сухой Нос, западный мыс Северного острова (73 °47' с. ш., 53° 45' в. д.). Продвигаясь на север, Баренц открыл о. Адмиралтейства (вторично после русских) и прошел пролив, отделяющий его от Новой Земли на 75° 54' с. ш. у острова голландцы «нашли обломок русского корабля», а за 76° с. ш. миновали голый «Остров с крестами» — так назвал его Баренц, увидевший там два креста; несомненно, их поставили русские на могилах или как опознавательные знаки. Вот как далеко на север заходили русские зверобои уже в XVI в. В этом районе голландцы впервые увидели лежбища моржей и встретили белого медведя. С 13 июля продвижение на север очень замедлилось.
29 июля Баренц открыл у 77° с. ш. «крайний северный мыс Новой Земли, названный Ледяным» (мыс Карлсена), а 1 августа близ него— небольшие Оранские о-ва. «...Моряки не желали идти дальше. Поэтому... он счел за лучшее... вернуться к другим кораблям, взяв курс к Вайгачу...» У Матвеева острова (69° 28' с. ш.) флотилия соединилась. Баренц был удручен «поражением», капитаны Най и Тетгалес ликовали. В сентябре все суда вернулись в Голландию. Два «победителя» были встречены с триумфом и возглавили в 1595 г. большую экспедицию. Баренц в ней был главным штурманом и капитаном одного из кораблей. Голландцы вернулись на родину, ничего не добившись.