Баренц был глубоко убежден в том, что морской путь на восток должен проходить севернее Новой Земли. Поэтому, выйдя из Норвегии, они взяли курс на север.
5 июня в 1596 г. путешественники встретили первый лед, а 9 июня подошли к незнакомому острову под 74°30′ с.ш. Здесь было собрано множество яиц чаек, а недалеко от берега убит громадный белый медведь, по которому и назвали остров – Медвежий. 13 июня взяли курс на северо-запад. 19 июня, под 80°11′ с.ш. с судов увидали полоску земли, которую голландцы приняли за Гренландию. Это была самая северная часть Шпицбергена. После недолгого совещания корабли вернулись на остров Медвежий, а затем суда разошлись. Ян Рийп пошел на север вдоль восточной стороны Шпицбергена, а Баренц отправился на восток и дошел до Новой Земли примерно на 75° с.ш. Ветер дул с юго-запада, море было почти полностью свободно ото льда, и настроение мореплавателей было прекрасным. В течение одной недели они прошли более 200 км в восточном направлении. 21 августа их движение остановил шторм, который принес за собой огромные массы льда и заставил капитана корабля укрыться в Ледяном заливе. 24 августа льдом раздробило руль у корабля и раздавило одну гребную лодку. На следующий день течение вынесло большую часть льда из бухты, и Баренц с товарищами опять вышел в море. Но вскоре напор льда опять усилился, и 26 августа корабль окончательно был остановлен льдами.
Голландцы находились ровно под 76° с.ш. «30-го числа, – записывает в своем дневнике де Фер, – при сильной вьюге льдины стали громоздиться вокруг нашего корабля, его приподняло льдом, который так его окружил, что все находившееся вблизи и вокруг него страшно трещало и стонало. Казалось, что корабль должен развалиться на тысячи кусков. Положение было такое ужасное, что у моряков волосы становились дыбом. В таком же опасном положении находился корабль еще и после, когда льдины подходили под него и его подталкивали, или его бросали, или его подымали, как будто подведена подъемная машина. Вскоре судно затрещало по всем швам до такой силы, что благоразумие требовало снять с него часть продовольственных запасов, паруса, порох, свинец, мушкеты и другое оружие и приступить к постройке бревенчатой избы».
Но еще две недели голландцы безуспешно пытались освободить судно из ледяного плена, пока наконец не осознали, что это им не под силу. Паковый лед давил все сильнее и сильнее, и они начали перетаскивать бочки с хлебом и вином и одну из лодок на лед. Но при этом путешественники все еще продолжали жить на борту судна. Прошло еще несколько дней, прежде чем они поняли, что этой осенью судно не сможет освободиться из ледяного плена, и что им придется зимовать, и что они бесполезно потеряли много драгоценного времени.