Затем в течение 30 лет Новая Земля не исследовалась вовсе. Лишь в 70-х годах прошлого века были предприняты несколько иностранных экспедиций, в частности немецкая (1872 г.), в которой принял участие профессор Леобенской горной академии Г. Гофер, шведская (1875 г.), в которой участвовал А. Э. Норденшельд, а также голландская на корабле «Вильгельм Баренц» (1878—1884 гг.). В этих экспедициях были добыты и первые геологические факты о новоземельских островах, но они касались только береговой полосы. В эти же годы русскими путешественниками были предприняты безуспешные попытки пересечь Новую Землю.
Приступив в мае 1895 г. к снаряжению экспедиции, Ф. Н. Чернышев включил в нее астронома Пулковской обсерватории А. А. Кондратьева и варшавского геолога И. А. Морозевича. Опыт Тиманской экспедиции показывал крайнюю необходимость в специалисте- топографе, но отпущенные на экспедицию средства не позволили включить его в состав экспедиции, и Феодосий Николаевич решил выполнять топографические работы сам вместе с А. А. Кондратьевым. Полагая, что обычные топографические съемочные работы мало что дадут в сложной орографической обстановке огромной территории, Ф. Н. Чернышев решил использовать новый в то время фотограмметрический способ съемки: «...для получения в короткий срок необходимых данных для построения карты внутренностей Новой Земли... благодаря лишь этому методу нам удалось охватить своими съемочными работами обширный район, и при этом в тот краткий срок, которым мы располагали на Новой Земле» [41]
.В состав экспедиции, кроме рабочего, взятого из Петербурга, были включены Василий Иглин, спутник Ф. Н. Чернышева по Тиманской экспедиции, а также мезенец Николай Петров, участвовавший в экспедиции Г. И. Танфильева на Тиман, и Кольский лопарь Филипп Архипов. Все эти люди, как писал впоследствии Феодосий Николаевич, вполне оправдали себя в сложной экспедиционной обстановке.
Архангельский губернатор считал лето 1895 г. особенно благоприятным для экспедиции на Новую Землю, так как в водах Северного Ледовитого океана предполагались рейсы трех паровых судов (военного клипера «Джигит», парохода Мурманского товарищества «Владимир» и парохода А. М. Сибирякова «Норденшельд»), которые могли оказать содействие в передвижении экспедиции.
5 июля Ф. Н. Чернышев со своими спутниками прибыл в Архангельск, и губернатор А. П. Энгельгардт сообщил ему, что уже 10 июля оба судна — «Джигит» и «Владимир» — отправятся на Новую Землю, однако они смогут сделать лишь одну переброску экспедиции, а в дальнейшем придется рассчитывать на собственные силы. Ф. Н. Чернышев заранее подозревал такой оборот дела, и по его просьбе директор мурманского пароходства П. И. Витт выделил для экспедиции хорошо оснащенный спасательный вельбот, который в дальнейшем очень выручил путешественников при изучении берегов Маточкина Шара, а также побережья к северу и югу от Кармакул.
Первоначально Ф. Н. Чернышев предполагал начать работы с Маточкина Шара, потом на «Джигите» перебраться в Крестовую губу, где была наибольшая вероятность встретить неразмытые угленосные слои. Затем Ф. Н. Чернышев планировал из Малых Кармакул сделать попытку пересечь Новую Землю и выйти к берегу Карского моря, а далее с помощью вельбота заняться изучением Гусиной Земли и Костина Шара с маршрутами в глубь острова.
10 июля экспедиция на «Владимире» вышла из Архангельска и в ночь с 14 на 15 прибыла в Малые Кармакулы — в то время фактический центр Новой Земли, в котором проживало около 30 семейств ненцев и имелись магазин и церковь. Поскольку «Владимир», прежде чем перебросить экспедицию в район Маточкина Шара, должен был' простоять два дня в Кармакулах, Ф. Н. Чернышев использовал это время для того, чтобы приготовиться к предполагавшемуся в начале августа переходу к Карскому морю. 16 июля «Владимир» вышел на север с экспедицией на борту, взявшей с собой лишь месячный запас провианта, и, выдержав сильный шторм, только в ночь на 18 июля вошел в Маточкин Шар, в Поморскую губу.
Лагерь разбили на морском берегу, у устья р. Маточки. С 18 июля начали работы на ближайших к лагерю возвышенностях — горах Пиле и Маточкиной. Вечером 19 июля прибыл «Джигит», который должен был перебросить экспедицию в Крестовую губу. Но на следующий день разыгрался шторм. Клипер, отдавший два якоря, был сорван и выброшен на камни у западного берега Поморской губы. Порывы ветра были столь сильны, что передвигаться по берегу можно было лишь ползком; палатки экспедиции забросало камнями. Лишь на второй день судно установило сообщение с экспедицией. После того как шторм утих, «Джигит» благополучно снялся с камней, но повреждения его были значительны, и он не смог перебросить Ф. Н. Чернышева к новому месту работ севернее Маточкина Шара.