Весной 1866 года Холл стал договариваться с иннуитами относительно участия их в походе. Это было делом очень нелегким, потому что эскимосы не понимали всей серьезности дела и относились к нему легкомысленно. Они то соглашались, то снова отнекивались от участия, и Холлу трудно было разобраться, на кого он может серьезно рассчитывать. В конце концов и этот вопрос уладился, и в марте месяце экспедиция была готова к отправке.
В записи Холла от последнего дня марта стоит: «Теперь к Земле короля Уильяма! В 4 часа утра мы готовы к отплытию». Участниками похода были, кроме Холла, Эбирбинга и Тукулиту, эскимосы Ормау, Нюкерцу с семьями, а также молодой Шенюкшу со своей матерью.
Когда путешественники выступили, погода была очень холодная, но ясная. С непривычки Холл сильно поморозил себе лицо, несмотря на то, что он прошел только три миля. Построили снежные домики — «иглу» — недалеко от жилища эскимоса Уэла. В хижинах поместился 21 человек. В течение следующих нескольких дней Холл и его спутники отсиживались в своих иглу, так как была страшнейшая пурга. В то время как Холл, сидя у себя в хижине, писал, держа случайно в своей руке нож, Уэла сообщил ему, что его соплеменники из Нейтчили имели много точно таких же, изготовленных из длинных и тяжелых ножей, но где были найдены последние, — он не знает. У Холла сейчас же мелькнула мысль, что эти «тяжелые» ножи были несомненно взяты с покинутых судов экспедиции Франклина.
Медленно продвигалась экспедиция вперед. Холл пересекал перешеек, в свое время открытый и нанесенный на карту доктором Рэ. Постоянные непогоды и болезнь ребенка Тукулиту вызывали частые задержки в пути. Лекарства, которыми Холл пытался лечить ребенка, не помогали, и тогда эскимосы обратились к помощи «ангеко», то есть шамана.
Имея много дела с иннуитами, Холл разгадал их характер и полюбил этих детей природы, несмотря на их недостатки. Он хорошо знал, что иннуиты всегда выручат его в трудном положении, но не создавал себе иллюзий насчет их послушания. Он не мог распоряжаться ими, как подчиненными; наоборот, ему приходилось зависеть от их доброй воли. В настоящий момент путешествие складывалось не вполне удачно, и было заметно некоторое недовольство иннуитов. Между тем, Холл рассчитал свою поездку на довольно продолжительный срок, и поэтому настроение иннуитов несколько беспокоило его. Насколько серьезно это путешествие было продумано, видно из того, что в письмах, написанных Холлом на родину еще до выступления в поход, он подробно перечислил места, где им будут положены сообщения, и указал, что нужно о ними сделать, если они будут найдены. Холл писал, что будет отсутствовать из области залива Репульс до следующей весны, а может быть и до будущего года. Сообщение о том, что будет сделано в районе этого залива, он положит у базы близ горы Бикощ а те, которые будут написаны во время пребывания на Земле короля Уильяма, — в тех пунктах, которые были использованы для этой цели Мак-Клинтоком во время экспедиции на «Фоксе». В большинстве же случаев свои сообщения он будет класть в 25 футах к северу от каменных гуриев, которые он поставит.
13 апреля снова пришлось остаться в хижине из-за свирепствовавшей бури. Весь день был посвящен угощению эскимосов и игре в домино. Вечером Холл возобновил свой разговор с Нюкерцу и его женой относительно экспедиции Франклина.
Тем временем препятствия на пути экспедиции все увеличивались. Теперь даже Эбирбинг проявлял нежелание двигаться дальше к Земле короля Уильяма. Эскимосы боялись, что не встретят там оленей и будут вынуждены вернуться на зиму к заливу Пелли. Холл старался ободрить их, говоря, что они будут там среди своих единоплеменников и найдут достаточно продовольствия. Он выказал твердую решимость итти вперед. В своем дневнике он заявляет, что если его даже оставят все эскимосы, он всё же один отправится с санной упряжкой, так как никогда не вернется на родину, не выполнив поставленной задачи, ради которой он ее покинул. Между тем, здоровье ребенка Тукулиту все ухудшалось, и Холлу было очень обидно, что этот маленький субъект приносит вред всему предприятию.
На следующий день, 18 апреля, Холл и сопровождавшие его эскимосы, позавтракав кофе с хлебом, снова отправились в путь. Они проходили по две мили в час и к четырем часам дня достигли пункта, находившегося в двух милях от моря. Спускаясь с горы к соленому озеру под углом в 45°, они выпрягли собак и пустили сани одни с нагруженной на них тяжелой поклажей.