Совсем не трудно было достичь Новой Земли из устья Печоры, откуда отправлялись промышленники на север охотиться на морского зверя. Итальянский учёный Юлий Помпоний Лэт, живший в конце XV века, писал: «На Крайнем Севере, недалеко от материка, находится большой остров; там редко, почти никогда не загорается день; все животные там белые, особенно медведи». Считается, что это первое письменное упоминание о Новой Земле. В следующем столетии европейцы уже не сомневались в том, что «холмогорцы ездят на Новую Землю ежегодно». Так говорилось в документе, относящемся к 1586 году.

Знаменитый Николай Витзен в своей книге «Север и Восток Тартарии», опубликованной в Амстердаме в 1705 году, ссылался на итальянского писателя Мавро Урбино, писавшего: «Русские, плавающие по северному морю, открыли около 107 лет назад остров, дотоле неизвестный, обитаемый славянским народом и подверженный... вечной стуже и морозу... Он превосходит величиной остров Кипр и показывается на картах под названием Новая Земля».

Название пролива Маточкин Шар появилось в 1598 году на карте Конрада Лёва, опубликованной в Кёльне. Первые сведения об этом проливе сообщены в сочинении «Записки о самоедах», напечатанном в Кёнигсберге в 1762 году: «...под 73° северной широты на восточной стороне, остров разрезается каналом или проливом, выходит в Северное море... Неизвестно, доступен ли этот пролив для мореплавания; он, несомненно, всегда бывает покрыт льдом...»

На европейских картах Новая Земля первоначально изображалась как очень большой остров, похожий даже на материк, распространяющийся далеко на восток и север. Более правильные очертания появились лишь на карте, составленной участником экспедиции В. Баренца Герритом де Фером в самом конце XVI века. Достаточно точно определена была северная оконечность островов, более или менее реальными стали контуры западного берега, восточный же берег, значительно более суровый и труднодоступный, долгое время оставался неизвестным.

Начало научному исследованию Новой Земли положила экспедиция Фёдора Розмыслова. Он отправился в 1768 году на острова проверить сообщение промышленника Якова Чиракина об узком «поперёк острова» проливе. Проливом этим можно было бы пройти в Карское море и дальше — на Обь и в Америку. Знать бы только, свободен ли он ото льда...

Кроме этого, экспедиции предписывалось «осмотреть в тонкости, нет ли на Новой Земле каких руд и минералов, отличных и неординарных камней, хрусталя и иных каких курьёзных вещей, соляных озёр и подобного, и каких особливых ключей и вод, жемчужных раковин, и какие звери и птицы, и в тамошних водах морские животные водятся, деревья и травы отменные и неординарные и тому подобных всякого рода любопытства достойных вещей и произращений натуральных».

У Фёдора Розмыслова была и научно-исследовательская программа. На трёхмачтовом судне водоизмещением около восьми тонн, называвшемся «кочмарой», экспедиция прибыла к входу в Маточкин Шар 25 августа 1768 года. Розмыслов провёл съёмку берегов залива, измерил его глубины. Выйдя к Карскому морю, он увидел его на редкость чистым, не заполненным, как обычно, льдами, за что издавна звали его моряки «ледовым погребом». Можно было плыть дальше на восток, вплоть до устья Енисея, но у старого судёнышка открылась сильная течь, на нём даже в Архангельск в пору осенних штормов возвращаться было рискованно: требовался ремонт. Розмыслов решил остаться на зимовку в проливе.

Избушку построили в Тюленьей бухте, потом ещё одну — на Дровяном мысу. Там умер в полярную ночь Яков Чиракин. Вскоре цинга скосила ещё трёх зимовщиков, больны были и остальные. Но всё же с восходом солнца Розмыслов продолжил съёмку берегов. Когда в августе пролив освободился ото льда, «кочмара» вышла в море, но, попав в полосу льда, снова получила пробоину. Пришлось вернуться в Маточкин Шар, где, к счастью, встретилась поморская лодья. На ней Розмыслов и его спутники вернулись в Архангельск, привезя с собой первую карту пролива, разделившего два острова Новой Земли.

Обо всём этом Литке читал в книгах и в рукописных отчётах, хранящихся в военно-морском архиве. Теперь ему самому предстояло преодоление препятствий, считающихся непреодолимыми. Бриг «Новая Земля» уже побывал у Новой Земли, но командовавший кораблём лейтенант А.П. Лазарев утверждал, вернувшись из плавания, что берега Новой Земли недоступны, и отказался продолжать работу. Собственно, Литке взялся за дело, признанное его предшественником безнадёжным.

Правда, молодому капитану не повезло в самом начале пути. Бриг медленно шёл по извилистому фарватеру в устье Северной Двины. Искусные лоцманы вывели его в море и туманным утром покинули корабль. Литке не уходил с мостика три ночи, но потом решил чуть-чуть отдохнуть, не успел он прилечь, как судно вздрогнуло от удара. Коварная мель, которой не было на карте! Дело осложнилось тем, что начался отлив и судно оказалось посреди осушенного дна, на острове, в полуверсте от схлынувшей воды. Матросы ходили вокруг по сухому песку.

Команды капитана были быстрые и чёткие. Следовало не пропустить момент прилива, подготовиться к тому, чтобы вывести судно. Наконец вода стала возвращаться. Литке вспоминал: «Все меры к спасению были приняты, и при полной воде бриг благополучно стянули с мели...»

Ледовитый океан встретил холодным ветром, тормозившим движение парусника, потом направление ветра переменилось, и бриг заскользил по свинцовым волнам на северо-восток. Но вскоре флотилия мощных льдин выстроилась на горизонте. Сначала их приняли именно за корабли, но это была ледовая защита острова, не пропускавшая к нему судно. Лавируя между льдинами, бриг медленно двигался, то и дело отступая назад. Особенно безнадёжной казалась ситуация ночью: «Нас окружали со всех сторон мелькавшие сквозь мрак, подобно призракам, ледяные исполины. Мёртвая тишина прерываема была только плеском волн о льды и изредка глухим воем моржей, всё вместе составляло нечто унылое и ужасное».

22 августа показалась куполовидная вершина, её назвали Первоусмотренная. Потом, когда этой горе нашли место на карте, она стала называться горой Сарычева. Две недели продолжалось преодоление ледяного барьера. Удалось прорваться и увидеть контуры земли, но подойти ближе оказалось невозможным. Её очертания не узнавал даже бывавший ранее на Новой Земле матрос Смиренников: вроде должен быть мыс Бритвина, но что-то не очень похож... Бриг продвигался дальше к северу. Вскоре появилась гора, похожая на храм с высокой колокольней. Литке решил дать ей имя Головнина, своего учителя, без участия которого, возможно, он и не попал бы в эти края.

Медленно, ложась то и дело в ледовый дрейф, шла «Новая Земля» на север вдоль неведомого берега: покрытые снегом хребты сменялись каменистыми утёсами; глубокие бухты — выступающими в море мысами. Стоял почти непрекращавшийся туман, из которого выныривали то редкие птицы, то морж, то тюлень. На берегу видели две избы, но людей около них не было. Литке искал пролив Маточкин Шар, но так и не нашёл его. Потом выяснилось, что бриг прошёл мимо, и не один раз, не заметив мыса.

Льды смыкались впереди, преграждая путь на север. Когда повалил густой снег и стало ясно, что наступает зима, было решено повернуть назад. До Архангельска шли ровно месяц.

Изучение полученного экспедицией материала показало, что она была не такой уж безрезультатной. Удалось вычертить значительный отрезок береговой линии Новой Земли. В докладе морскому министру Литке признал свои ошибки в этом походе, вполне объясняемые отсутствием опыта и поздним выходом в море. Но главная цель всё же была достигнута: удалось опровергнуть представление о недоступности островов. «При всём неуспехе своём, экспедиция сия доказала совершенную неосновательность мнения, будто бы берега Новой Земли от накопившихся годами льдов сделались недоступными...»

Так закончил Литке свой доклад морскому министру маркизу де Траверсе. Прочитав его, министр решил, что следует на будущий год дать молодому капитану новое, более сложное задание. Начать работу следовало уже весной: сначала у западных берегов Белого моря, в Лапландии. А в середине лета, когда станет возможным плавание во льдах Баренцева моря, было приказано отправиться к Новой Земле и «непременно достигнуть её северной оконечности и, определив широту оной, возвратиться к Маточкину Шару...»