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