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 км и там есть отличная гавань.