В течение первых трех недель марта Холл старательно готовился к походу. К несчастью, он лишился всех своих собак, добытых с таким трудом. Среди них развилась какая-то эпидемия, собаки стали дохнуть одна за другой, некоторых пришлось пристрелить, и в конце концов не осталось ни одной. Счастье еще, что Холлу удалось закупить пять собак у иннуитов, иначе и это путешествие провалилось бы. В бухте Таллун Холл оставил в устроенном здесь лагере четырех из пяти своих белых помощников, среди которых были два матроса по фамилии Бейн и Колеман. Он поручил им охоту на зверей и велел дожидаться своего возвращения.
23 марта 1868 года Холл выступил в поход в сопровождении одного английского матроса — Франка Лейлора, Эбирбинга, Тукулиту, эскимоса Папа и его жены с маленьким ребенком. Уже в самом начале путешествия приключилась маленькая неприятность: сильнейшим ветром с саней сдуло последний дневник Холла, который заметил случившееся только в тот момент, когда Папа был уже на льду и гнался во весь опор за улетавшими листками. После тщетных попыток поймать их. Папа вернулся разгорячившийся и усталый. Потеря была непоправимой.
2 апреля Холл и его спутники прибыли на берег канала Фокса и построили здесь свое «иглу» десятое по счету. Здесь было оставлено некоторое количество хлеба и пеммикана для обратного пути от пролива Фьюри и Гекла. 6 апреля экспедиция прибыла к острову Углит, населенному большим количеством эскимосов. Здесь Холл остановился на несколько дней, не столько чтобы отдохнуть, сколько чтобы запастись моржовым мясом и расспросить туземцев обо всем, что они знают о белых людях с пропавших кораблей.
Во время пребывания на острове Углит к Холлу в его иглу заходило много местных жителей. Расспрашивая каждого из них в отдельности, а потом сразу целую группу, Холл еще больше уверился в том, что сообщения относительно белых, которых видели на южном берегу пролива, отвечают истине. Он серьезно надеялся, что скоро увидит нескольких спутников Франклина, оставшихся еще в живых.
Холл подробно заносил эти беседы в свой дневник, по несчастной случайности впоследствии затерявшийся. Однако некоторые места были потом восстановлены по копии, снятой одним из его друзей. Из этих отрывков можно видеть, что именно вызвало энтузиазм Холла и побудило его продолжать путешествие. Вот обстоятельства этого дела:
«Хотя Холлу и не удалось разыскать Киа, убитого моржом во время охоты, он узнал от Кулуа, эскимоса, которого Холл считал заслуживающим полного доверия, что когда он охотился в местности между бухтой Гарри и северо-западным мысом полуострова Мельвиля, он видел «иннукшу», то есть, памятник, на южном берегу реки, впадающей в залив несколько западнее мыса Эллис. Памятник был сложен из камней, часть которых была сдвинута с места. Судя по внешнему виду, он был сооружен недавно. Ничто не указывало на то, что там было сложено продовольствие. Кулуа не допускал, что памятник был сложен эскимосами, так как он был первым из них, зашедшим так далеко от залива Гарри. Киа рассказывал ему, что он видел там чужеземца. У него была шапка на голове и одежда с капюшоном. Киа некоторое время наблюдал за ним, прячась за скалами. Потом он слышал ружейный выстрел».
Все иннуиты острова Углита верили рассказу Киа, что и подтвердили в беседе с Холлом. Кроме того, ему передавали столь же странные рассказы о чужеземцах, которых видели поблизости от Иглулика, и о звуках, напоминавших ружейные выстрелы, которые неоднократно были слышны в таких местах, где происхождение их нельзя было объяснить треском расколовшихся льдин. Эскимосы приняли неизвестных первоначально за индейцев, что так испугало их, что они немедленно покинули эти места. Следы, оставленные чужеземцами, были длинными, суживавшимися к середине и более глубокими у пятки.
Холл не мог не сопоставить рассказов о корабельной мачте и бревнах, найденных на берегу около залива Пелли — памятнике, о котором говорил Сипунгир, повидимому до сих пор стоявшем на северном берегу пролива, с сообщениями о странном появлении незнакомцев, их одежде и оставленных ими следах. Он высказывал предположение, что некоторые из спутников Франклина переправились на восток от области Парри, может быть в надежде добраться этим путем до пролива Кумберлэнд, где они рассчитывали найти какой-нибудь английский корабль. И эти люди могли быть еще в живых, так как по рассказам о последних встречах туземцев с белыми чужеземцами они якобы происходили в 1864 году.
16 апреля Холл выступил из Углита. С экспедицией отправился в качестве гида иннуит Кулуа. Переход до места, где предполагалось найти памятник, занял восемь дней.