Весенние месяцы прошли в привычных уже тяготах, и в конце мая команда обратилась к Баренцу и Хемскерку с вопросом: не пора ли покинуть, наконец, злополучную Ледяную гавань. Штурман «мастер Виллем», хотя и был тогда уже болен, согласился и начал активно давать советы и распоряжения, чтобы сделать это. Понимая, что на прочно засевший среди торосов корабль рассчитывать не приходится, он придумал дерзкий, но, как выяснилось, отнюдь не безрассудный способ добраться до материка на тех самых двух лодках, что сняли с судна осенью. К большому испытанию их готовили тщательно: законопатили щели, поставили небольшие мачты, борта нарастили последними оставшимися досками, причем делали все это только 12 человек — остальные трое, среди которых был и Виллем Баренц, увы, находились уже в той стадии болезни, что не могли физически работать.
Чтобы подтащить лодки к открытой воде, пришлось еще и пробивать дорогу — несколько сот метров через торосистые льды. Затем к ботам притащили все, что осталось из еды и одежды, на руках перенесли умирающих. Впрочем, для Баренца еще оставалось одно важное дело на Земле. День отплытия был назначен Хемскерком, но перед этим именно шкипер написал записку с детальным изложением всех злоключений, постигших голландцев во время плавания и зимовки. Ее вложили в мушкетную гильзу и спрятали среди камней очага. Столетия спустя англичанин Гардинер обнаружит это послание и прочтет: «Дела будут не вполне благополучны как из-за длинного пути, который предстоит нам проделать, так и потому, что с хлебом не дотянуть до конца августа, а между тем легко может выйти, что если с нами случится в пути что-нибудь скверное, то раньше этого времени мы не доберемся ни до какой страны, где могли бы приобрести что-либо. В силу всего этого мы решили не ждать более, так как и сам Господь учит нас думать о спасении».
14 июня 1597 года при попутном ветре «утлые челны» покинули злополучную гавань, взяли курс на северо-восток и к вечеру следующего дня достигли Оранских островов. Такой быстрый успех стал возможен исключительно благодаря карте севера и запада Новой Земли. Ее всю зиму составлял собственноручно Баренц. Пригодились многолетние уроки Планция — карта эта считалась самой точной вплоть до XIX столетия. По пути не пришлось даже терпеть голод — морякам попадалось множество птичьих яиц. Собирая их, чуть не погиб сам капитан Хемскерк — он провалился под лед, но смог самостоятельно выплыть.
Ободренные удачей, голландцы продолжали свой путь. Правда, уже в западном море, которое позже заслуженно получит имя Баренца, в районе Ледяного мыса (сейчас — залив Иванова), шлюпы оказались окружены плотным льдом, и усталым людям показалось, что на сей-то раз им точно пришел конец. Но тут их неожиданно выручил мужественный Геррит де Фер. Чтобы избежать гибели, надо было каким-то образом закрепить канаты на припае и с их помощью вытянуть боты на лед. И де Фер, самый легкий и, видимо, самый ловкий из них, перепрыгивая с льдины на льдину, сумел справиться с этой задачей — спас себя и товарищей.