Приехавшие издалека эскимосы рассказывали в свое время Холлу, что два года тому назад мимо их селения проплыли две лодки с командой из чужеземцев. На них было много провизии, пороху и прочих огнеприпасов, люди были вооружены ружьями. Эскимосы подробно рассказывали, что делали эти путешественники и как они ушли. Холл решил, что это могли быть люди с «Эребуса» и «Террора», которые держали свой путь от Земли короля Уильяма через Бутию на восток. Однако впоследствии оказалось, что это предположение было неверно, так как выяснилось, что обе лодки принадлежали экипажу корабля, раздавленного льдами в Гудзоновом проливе в 1859 году.

Наиболее ценным приобретением, сделанным Холлом во время его пребывания на Баффиновой земле, были, конечно, Тукулиту и Эбирбинг, которых ему удалось привлечь к своему делу. Еще весной 1861 года супруги явились к Холлу со всеми своими пожитками, с тем, чтобы сопровождать его в намеченном лодочном походе к Земле короля Уильяма. Эта поездка, как известно, не состоялась. Тогда оба эскимоса предложили свои услуги в качестве переводчиков для задуманной Холлом будущей экспедиции. Они прибыли вместе с Холлом в Америку и приняли деятельное участие во всех подготовительных работах.

Готовясь к следующему своему путешествию, Холл проявил энергичную деятельность. О момента возвращения его из первой экспедиции прошло более полутора лет. За этот период Холл успел написать две объемистых книги о своей жизни среди эскимосов и наблюдениях над их бытом.

В конце июля 1864 года Холл вышел в море на корабле «Монтичелло», которым командовал тот же капитан Беддингтон.

Холл покидал цивилизованный мир в грустном сознания того, что, кроме него, никто не пытается больше разгадать судьбу пропавших людей. Но тем сильнее была у него надежда и желание добиться успеха в своем предприятии. В день отправления, уже на борту «Монтичелло» он записал в свой дневник:

«Снова я возвращаюсь в их страну, но теперь я могу разговаривать с ними, я могу жить среди них, я умею вести их образ жизни. Я научился кочевать с ними с места на место и смогу терпеливо изучать все страны, где можно предположить, что проходили и гибли люди Франклина.

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

«Монтичелло» взял курс через Гудзонов пролив на бухту Репульс. В конце августа корабль прибыл в пролив Роус Уэлком. 31-го Холл высадился в том месте, где ответвляется узкий залив Уэгер. Время было уже позднее, и Холл не рассчитывал успеть в этом году произвести обследование района. Со своими помощниками, Эбирбингом и Тукулиту, он приступил к постройке снеговых хижин, по примеру эскимосских.

Из залива Репульс к нему пришли эскимосы, и Холл не преминул расспросить их обо всем, что они знают об экспедиции Франклина. Холл очень доверял словам туземцев, в противоположность большинству полярных путешественников. На этот раз он был очень обрадован, услышав от них рассказ, мало чем отличающийся от официальной версии. В этом он видел доказательство точности, которой придерживаются эскимосы при передаче фактов. Холлу быстро удалось наладить хорошие отношения с ближайшими семьями иннуитов, которым он помогал в их недугах, исполняя роль лекаря.

Перезимовав в проливе Роус Уэлком, Холл летом 1865 года перебрался в бухту Репульс. Он объехал на шлюпке всю бухту и внимательно осмотрел ее. Этим и ограничилась вся его поисковая деятельность этого лета, ничего существенного не принесшая. Холл особенно не спешил, он хотел привыкнуть к обстановке и к людям, учитывая при этом, что в предстоящем путешествии к Земле короля Уильяма ему придется пользоваться исключительно услугами иннуитов.

С осени Холл начал подготовку большого санного путешествия, рассчитанного на будущую весну. Он поставил своей задачей во что бы то ни стало достигнуть Земли короля Уильяма. Вторая зимовка была труднее первой, так как на этот раз в ближайшей окрестности не было эскимосов. Только Эбирбинг, Тукулиту и еще одна иннуитская семья жили вместе с ним. Работы было много, так как необходимо было заготовить достаточное количество провизии для предстоящего путешествия. Нелегко было также прокормить всех в течение долгой зимы. Холл успешно участвовал в охоте на оленей, ему удалось заготовить большое количество мяса, которое складывалось в специальное депо. Кроме того, Холл вместе с эскимосами занимался рыбной ловлей и охотой на тюленей и заготовлял одежду и сани для предстоящей поездки.

Весной 1866 года Холл стал договариваться с иннуитами относительно участия их в походе. Это было делом очень нелегким, потому что эскимосы не понимали всей серьезности дела и относились к нему легкомысленно. Они то соглашались, то снова отнекивались от участия, и Холлу трудно было разобраться, на кого он может серьезно рассчитывать. В конце концов и этот вопрос уладился, и в марте месяце экспедиция была готова к отправке.

В записи Холла от последнего дня марта стоит: «Теперь к Земле короля Уильяма! В 4 часа утра мы готовы к отплытию». Участниками похода были, кроме Холла, Эбирбинга и Тукулиту, эскимосы Ормау, Нюкерцу с семьями, а также молодой Шенюкшу со своей матерью.

Когда путешественники выступили, погода была очень холодная, но ясная. С непривычки Холл сильно поморозил себе лицо, несмотря на то, что он прошел только три миля. Построили снежные домики — «иглу» — недалеко от жилища эскимоса Уэла. В хижинах поместился 21 человек. В течение следующих нескольких дней Холл и его спутники отсиживались в своих иглу, так как была страшнейшая пурга. В то время как Холл, сидя у себя в хижине, писал, держа случайно в своей руке нож, Уэла сообщил ему, что его соплеменники из Нейтчили имели много точно таких же, изготовленных из длинных и тяжелых ножей, но где были найдены последние, — он не знает. У Холла сейчас же мелькнула мысль, что эти «тяжелые» ножи были несомненно взяты с покинутых судов экспедиции Франклина.

Медленно продвигалась экспедиция вперед. Холл пересекал перешеек, в свое время открытый и нанесенный на карту доктором Рэ. Постоянные непогоды и болезнь ребенка Тукулиту вызывали частые задержки в пути. Лекарства, которыми Холл пытался лечить ребенка, не помогали, и тогда эскимосы обратились к помощи «ангеко», то есть шамана.

Имея много дела с иннуитами, Холл разгадал их характер и полюбил этих детей природы, несмотря на их недостатки. Он хорошо знал, что иннуиты всегда выручат его в трудном положении, но не создавал себе иллюзий насчет их послушания. Он не мог распоряжаться ими, как подчиненными; наоборот, ему приходилось зависеть от их доброй воли. В настоящий момент путешествие складывалось не вполне удачно, и было заметно некоторое недовольство иннуитов. Между тем, Холл рассчитал свою поездку на довольно продолжительный срок, и поэтому настроение иннуитов несколько беспокоило его. Насколько серьезно это путешествие было продумано, видно из того, что в письмах, написанных Холлом на родину еще до выступления в поход, он подробно перечислил места, где им будут положены сообщения, и указал, что нужно о ними сделать, если они будут найдены. Холл писал, что будет отсутствовать из области залива Репульс до следующей весны, а может быть и до будущего года. Сообщение о том, что будет сделано в районе этого залива, он положит у базы близ горы Бикощ а те, которые будут написаны во время пребывания на Земле короля Уильяма, — в тех пунктах, которые были использованы для этой цели Мак-Клинтоком во время экспедиции на «Фоксе». В большинстве же случаев свои сообщения он будет класть в 25 футах к северу от каменных гуриев, которые он поставит.

13 апреля снова пришлось остаться в хижине из-за свирепствовавшей бури. Весь день был посвящен угощению эскимосов и игре в домино. Вечером Холл возобновил свой разговор с Нюкерцу и его женой относительно экспедиции Франклина.