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