5 июля 1594 г. Най с отрядом кораблей отправился из Текселя в море, назначив Баренцу, который еще не совсем был готов, встречу за островом Кильдин. Первый прибыл сюда 21-го, а последний – 23 июня. 29 июня Баренц отправился в свой путь к северо-востоку.

17 июля он увидел берег Новой Земли под 73° 25′ с.ш. Пристав к берегу в обширной Софроновой губе, он нашел здесь следы пребывания людей. Двигаясь к северу, Баренц миновал большую бухту, которую по встреченным там в изобилии птицам назвал «Lomsbay». По-видимому, это нынешняя Крестовая губа.

19 июля корабли Баренца дошли до Черного Мыса под 75° 20′ с.ш. В 60 км отсюда был открыт остров Вильгельма, принадлежащий к группе Горбовых островов. Здесь он встретил много сплавного леса и лежбища моржей. Широту острова он определил в 75° 55′ с.ш., на десять минут севернее, чем впоследствии у капитана Литке.

10 июля Баренц увидал голый Крестовый остров под 76° с.ш. и через 60 км достиг мыса Нассау – отлого низменного и очень опасного из-за множества окружающих его подводных рифов. Уже 26 июля путешественники встретили первые ледяные поля. Проходя у берега и они добрались до мыса Утешения. 29 июля под широтой 77° они увидали по направлению к востоку одну из северных оконечностей Новой Земли, которую назвали Ледяным Мысом. 13 августа Баренц дошел до острова Орамина и здесь остановился. Море было покрыто сплошными массами льда, и команда начала роптать, поэтому Баренц уже 14 августа пустился в обратный путь, на встречу с отрядом Ная.

В свою очередь, Най 15 июня вышел из Кильдина к востоку. Через три дня он наткнулся под 71° 20′ с.ш. на плавучий лед и такой густой туман, что принял его за землю. 7 июля он подошел к берегу полуострова Канина. В последующие два дня опять появился сильный лед, двигавшийся из большого залива между мысами Канин и Святой Нос (Чешская губа).

9 июля Най встретил четыре русские ладьи, направлявшиеся к устью Печоры. Моряки отсоветовали ему идти к Югорскому Шару, потому как он «заполнен льдами, подводными камнями, а равно моржами и огромными китами, угрожающими судам опасностью». Голландцы, однако, не послушались и 16 июля пошли далее на восток при теплой, даже жаркой погоде и снова встретили ладью с русскими рыбопромышленниками. Голландцы узнали, что до устья Печоры 81 км и там есть отличная гавань.

18 июля они вошли в Печору, бросили якорь на глубине 11 метров и переждали там сильную бурю с северо-востока. 21 июля в 220 км от Печоры они увидали остров Вайгач. Море на всем пространстве было покрыто плавучим лесом, громадными стволами с корнями и сучьями, по их предположению, сплавляемыми по какой-либо большой реке. Подходя к острову, они были поражены обилием трав и цветов.

Проплыв еще 22 км, путешественники открыли пролив в 7 км ширины, с островом в середине. Най полагал, что это пролив, отделяющий остров Вайгач от материка. Как только они бросили якорь, Най послал гребные суда для измерения глубины. Сильное течение, пригонявшее множество льда, утвердило его в том, что они находились в проливе. Это был Югорский Шар. На берегу острова Вайгач они нашли более 400 идолов грубой работы, поэтому и назвали это место Мысом Идолов (Болвановский Нос).

1 августа Най с товарищами прошли в открытое море (Карское), которое назвали Новым Северным морем. Там путешественников встретил такой сплошной лед, что они уже хотели повернуть обратно, но, на их счастье, увидали небольшой остров (Мясной). На нем было много горного хрусталя, похожего на отшлифованные бриллианты. Опять показался плавучий лед. Пройдя далее, они увидали низменный берег. К югу открывался залив, в который впадала большая река, которую они приняли за Обь. Най решил, что берег отсюда тянется до мыса Табина и далее до Китая и что задача их решена. Прибрежное пространство между проливом Нассауским и мнимою рекою Обью они назвали Новою Голландией. Было решено прекратить дальнейшее путешествие и пуститься в обратный путь. 28 августа Най встретился с Баренцем, а в конце сентября суда бросили якорь на родине, у острова Текселя.