Навалившиеся трудности практически сразу помешали поискам, и яхта была вынуждена провести первую зиму в скованном льдами Баффином заливе. К августу 1858 г. «Фокс» дошла до острова Бичи — места первой зимовки Франклина, и Мак-Клинток установил там памятник от имени леди Франклин. Монумент датировался 1855 г., и на нем была высечена надпись:

«Памяти Франклина, Крозье, Фицджеймса и всех их доблестных товарищей, офицеров и верных сослуживцев, пострадавших и погибших за дело науки и во славу Родины. Этот памятник поставлен близ места, где они провели первую полярную зиму и откуда выступили в поход, чтобы преодолеть все препятствия или умереть. Он свидетельствует о памяти и уважении их друзей и соотечественников и о скорби, утоляемой верою его супруги, утратившей в лице начальника экспедиции преданного и горячо любимого мужа».

К концу сентября поисковики вышли к западному входу пролива Белло, где они организовали вторую зимовку. Отсюда в начале апреля 1859 г. Мак-Клинток и Гобсон с небольшим отрядом двинулись в поход на остров Кинг-Уильям. Затем они разделились на две группы: Гобсон по приказу Мак-Клинтока изучал западный берег острова, в то время как сам Мак-Клинток пошел к его восточному берегу, к устью реки Бака, и вернулся потом со стороны западного побережья.

20 апреля Мак-Клинток встретил две семьи инуитов. Он выменял у них вещи Франклина и, расспросив, узнал, что они видели два корабля. Один затонул в глубокой воде, второй разбился о береговые торосы. На борту они нашли тело очень большого человека с «длинными зубами». Они рассказали, что «белые люди ушли к „большой реке“ с лодкой или лодками, а следующей зимой они нашли их кости». Позже Мак-Клинток встретил группу из тридцати-сорока инуитов, которые проживали в деревне на острове Кинг-Уильям.

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

Отряд Мак-Клинтока дошел до материка и продолжил свой путь на юг, к острову Монреаль, где нашел еще несколько вещей, в том числе часть от жестяной банки из-под консервированного мяса, два куска железного обруча и несколько кусков металла. После этого санная партия вернулась на остров Кинг-Уильям. Жуткие тайны поджидали группы и Мак-Клинтока, и Гобсона на их пути по заснеженной земле.

Вскоре после полуночи 24 мая 1859 г. на песчаном хребте вблизи устья реки Пеффер на южном берегу острова им попался человеческий скелет, на котором еще сохранились остатки формы стюарда корабля пропавшей экспедиции. Мак-Клинток описал эту трагичную сцену в дневнике:

«Этот бедный человек выбрал голую вершину хребта в качестве последнего пристанища после утомительного похода и упал лицом вниз. Там мы его и обнаружили. Весь ужас в том, что все было так, как рассказывала пожилая женщина: „Они падали и умирали на ходу“».

Мак-Клинток верил, что мужчина уснул вечным сном в такой позе и что в свои «последние мгновения он не мучился».

Рядом с выбеленным скелетом лежали «маленькая щетка для одежды и карманный роговой гребешок, на котором еще остались несколько коричневых волосков». Была еще записная книжка, принадлежавшая Гарри Пеглару, старшине на корабле «Террор». В ней обнаружили записи двумя разными почерками — Пеглара и второго, неизвестного. Рукой Пеглара было записано стихотворение, датированное 21 апреля 1847 г., которое начиналось словами «The С the С the open С it grew so fresh the ever free» — «Море, море, открытое море, оно свежо и навеки свободно» (видоизмененное стихотворение Барри Корнуолла «The Sea», — прим. пер.). Загадка содержалась в других записях, принадлежавших руке неизвестного. Они явно имели отношение к катастрофе. Большинство слов в сообщении были написаны задом наперед и заканчивались заглавными буквами, как если бы конец был началом. На одном листке был набросок с изображением глаза и подпись внизу «Залив Веко» (Lid Вау). Следующее послание содержало такое сообщение: «О, Смерть, где твое жало? Могила в бухте Успокоения для тех, у кого остались сомнения, как… сказал умирающий». С другой стороны листка слова были написаны по кругу, а внутри — надпись: «Лагерь ужасов пуст». Было решено, что это название места и оно относится к временному лагерю, разбитому экспедицией Франклина — возможно, лагерю на острове Бичи. Другой листок, написанный тем же почерком, тоже задом наперед, имел следующее содержание: «Если бы у нас были самые серьезные причины, чтобы покинуть… нам нужно было бы немного грога, чтобы промочить… Все, что я мог, Том, поскольку я думаю… время… я задремал, должен положить и… 21-я ночь…». Должно быть, имелось в виду 21 апреля 1848 г. — канун ухода с «Эребуса» и «Террора». Догадка родилась благодаря одной ценной находке. Самый важный артефакт в поисках Франклина был обнаружен тремя неделями раньше, еще до того, как наткнулись на скелет. 5 мая в гурии на мысе Виктори Пойнт нашли единственный отчет экспедиции Франклина, описывающий события после ухода с кораблей. И состоял он из двух записей, сделанных корявым почерком на бланке Адмиралтейства.

Первая была сделана лейтенантом Грэмом Гором и докладывала об успехах экспедиции до мая 1847 г.:

«28 мая 1847 г. Корабли Ее Величества „Эребус“ и „Террор“ зимовали во льду в 70° 5′ с. ш. и 98° 23′ з. д. Перезимовали в 1846-47 на о. Бичи 74° 43′ 28″ с. ш. и 91° 37′ 15″ з. д. после того, как поднялись по проливу Веллингтона до широты 77° и вернулись вдоль западной стороны острова Корнуоллис. Сэр Джон Франклин командует экспедицией. Все в порядке. Партия из 2 офицеров и 6 матросов покинула корабли в понедельник 24 мая 1847 г. Грэм Гор, лейтенант, Ш. Ф. де Ве, помощник капитана».