Более недели экспедиция провела вблизи мыса Нассау. Только 9 июля путешественники снова поставили паруса. Однако плавание было непродолжительным. На следующий день пришлось снова вытащить лодки и ждать того момента, когда ветер отгонит льды от западного берега Новой Земли.
Смерть Баренца продолжала остро ощущаться членами экспедиции. В эти трудные дни очень недоставало этого мужественного человека, умевшего веселым словом подбодрить своих товарищей. Настроение моряков было подавленное. Они уже потеряли пять человек и серьезно опасались, что скоро не хватит сил перетаскивать лодки через перемычки льдов. Правда, мореплаватели жили надеждой, что около Крестовых островов они встретят русских. Но ожидания их были напрасны. Они не нашли на островах промышленников, но зато обнаружили несколько гнезд горной гаги, в которых нашли более 70 яиц. С большой осторожностью доставили в лагерь эту драгоценную находку. Впервые за много дней путешественники наелись досыта.
Вблизи Крестовых островов экспедиция задержалась на восемь дней. 19 июля трое моряков поднялись на высокий горный берег и увидели, что до самого горизонта голубеет чистая вода. Перетащив по льду лодки, путешественники возобновили плавание. Несколько дней плыли с попутным ветром, не встречая каких-либо препятствий. Льдов не было видно даже на горизонте. Путь на юг был открыт. Яков Гемскерк и его спутники приободрились, считая что самые большие трудности остались позади и что скоро они доберутся до мест, часто посещаемых русскими.
Спустя пять дней экспедиция прибыла в залив Моллера и по случаю ненастной и ветреной погоды укрылась в хорошо защищенной гавани. На скалах, окружавших ее со всех сторон, находился птичий базар. Рискуя поломать руки и ноги, моряки взобрались на утесы и собрали 125 кайр. Яйца в гнездовьях оказались насиженными, и их не трогали.
Скоро погода прояснилась и шлюпки опять вышли в море. Несколько дней плавание проходило при благоприятных условиях. Встречавшиеся полосы льда не задерживали шлюпки. 28 июля миновали Костин Шар, расположенный у юго-западного побережья Новой Земли, и, обогнув мыс Шанца, увидели две русские ладьи и находившихся поблизости от них промышленников.
После тринадцати месяцев плаваний в полярных водах и жизни на пустынной Новой Земле голландцы, наконец, встретили людей. Это была большая радость, окрылявшая верой в благополучный исход путешествия.
Среди встреченных поморов Геррит де-Фер и Яков Гемскерк, участвовавшие в плавании 1595 года, узнали знакомых, с которыми два года назад свела их судьба на берегу острова Вайгач. Русские, узнав, что голландцы потеряли во льдах корабль, сочувственно отнеслись к их горю и поделились запасами своего продовольствия.