Время открытия русским Новой земли исследователи относят к XII-XV векам. Первые письменные свидетельства о пребывании и промысловой деятельности русских на архипелаге относятся к 16 веку и принадлежат иностранцам.

Бесспорные материальные свидетельства давнего пребывания русских на Южном и Северном островах архипелага были зафиксированы в 1596-1597 гг. в дневниках Де-Фера - участника голландских экспедиций под руководством Виллема Баренца.

Русских поморов привлекали на Новую Землю разнообразные богатые промыслы. Они добывали: моржовые клыки; песцовые, медвежьи, моржовые, тюленьи и оленьи шкуры; моржовое, тюленье, белушье и медвежье "сало" (ворвань); омуля и гольцов; гусей и других птиц; гагачий пух. Ранним летом отправлялись на промышленных судах своеобразные артели от 8 до 20 человек их Белого моря, с Мезени и Печоры к островам Новой Земли. Ходили из года в год, что способствовало формированию целых династий новоземельских промышленников и мореходов. Ходили на лодьях, кочах и карбасах - небольших судах, команду которых возглавлял кормщик. Зачастую, ледовая обстановка, сильные штормы, гибель судна заставляли промышленников зимовать на Новой Земле. Часть из них гибла, другие выживали, набирались опыта. Для строительства жилья и его обогрева первоначально использовался только плавник. Затем начали брать с собой разнообразные срубы (для установок в местах зимовки) и запас дров.

В зимнее время основным промыслом поморов становилась ловля песцов при помощи ловушек - кулем. Кулемы сооружались вдоль побережья, на большом протяжении. Чтобы вовремя осматривать кулемы, промышленники ставили на расстоянии 5-10 км от становой избы (и друг от друга) несколько разволочных изб, на 2-3 человека.

Соорудив становую избу с печкой-каменкой, нарами и сенями, рядом воздвигали многометровый поклонный (приметный) крест. Неподалеку, или вплотную к избе, строили баньку и "шалаш" из бревен для хранения запасов провианта и добычи. Крест служил своеобразным знаком-маяком многие годы. В этот же сезон, или в последующие, на побережье, обычно, воздвигалась целая система поморских крестов и гуриев, которые служили створами, маяками и указывали судам безопасные подходы к месту стоянки.

Господство Испании и Португалии на южных морских путях в Индию вынудило английских мореплавателей искать северо-восточный проход в страны Востока. В 1553 г. Х. Уиллоуби вышел из Англии и, по-видимому, достиг южного побережья Новой Земли. Повернув назад, два корабля экспедиции вынуждены были зазимовать у устье реки Варсины на восточном Мурмане. В следующем году поморы случайно наткнулись на корабль с трупами 63 английских участником зимовки. В 1556 г. английское судно под командованием С. Барроу достигло берегов Новой Земли, где встретило команду русской лодьи. Скопление льда в проливе Югорский Шар вынудило экспедицию вернуться в Англию. В 1580 г. английская экспедиция А.Пита и Ч.Джекмена на двух судах дошла до Новой Земли, но сплошной лед в Карском море заставил плыть на родину.

В 1594-1596 гг. из Голландии направляются северо-восточным проходом три торговых морских экспедиции в Индию и Китай. Одним из из руководителей всех трех экспедиций был выдающийся голландский мореплаватель Виллем Баренц. В1594 г. он вдоль северо-западного побережья Новой Земли достиг её северной оконечности. По пути голландцы неоднократно встречали материальные свидетельства пребывания русских на Новой Земле. Команда Баренца не захотела идти дальше в Карское море, и судно вернулось на юг, к Югорскому шару, где стояли два голландских судна. В 1995 г. Баренц вновь участвует в экспедиции, в которую входило шесть голландских судов.

Им удалось пройти Югорским шаром в Карское море, но льды не пропустили дальше острова Местного. Суда повернули на запад. В 1596 г. снова два судна были направлены Голландией в Китай северо-восточным путем. Баренц решил обогнуть Новую Землю с севера, второе судно пошло другим маршрутом и вернулось к Мурманскому полуострову. 26 августа 1596 года судно Баренца было затерто у северо-восточного побережья архипелага, в Ледяной Гавани. Голландцам пришлось выстроить на берегу жилище из плавника и судовых досок для зимовки. 14 июня 1597 г., бросив судно, голландцы отплыли на двух лодках из Ледяной Гавани У северо-западного побережья Новой Земли , в районе залива Иванова В.Баренц скончался, Оставшиеся в живых 12 голландцев на лодках дошли до Колы, встретились со вторым судном экспедиции на нем 30 октября 1597 года прибыли в Голландию.

В 1652 г. по указу царя Алексея Михайловича на Новую Землю отправилась экспедиция Романа Неплюева для поиска серебряных и медных руд, драгоценных камней и жемчуга. Большинство из 83 участников и сам Неплюев погибли во время зимовки южнее острова Долгий. В 1671 г. на поиски серебряной руды и для строительства на архипелаге деревянной крепости была направлена на Новую Землю экспедиция под руководством Ивана Неклюдова. В l672 г. все участники экспедиции погибли.