6 февраля 1825 года экспедиция отправилась из Фалмута на Мальту. В ее состав входили кроме самого Лэнга Джек ле Бор и два судовых плотника — африканцы с западного побережья, Харрис и Роджерс. Лэнг взял их с собой, так как думал, добравшись до Томбукту, построить там судно и на нем спуститься до впадения реки в океан. Во время двухмесячного пребывания на Мальте, посвященного пополнению экспедиционных запасов и лечению (Лэнга мучила болезнь печени, которой он страдал еще со времени службы в Вест-Индии), он узнал о благополучном возвращении экспедиции Клаппертона и Денэма. Письма друзей из Англин рассказывали и о новой экспедиции Клаппертона, которая должна была вот-вот отправиться от побережья Гвинейского залива на север все с тем же заданием — выяснить наконец, куда впадает Нигер. Новости эти, с одной стороны, радовали Лэнга, а с другой — причиняли ему некоторое беспокойство: он очень боялся, что Клаппертон лишит его приоритета открытия устья. А на такой приоритет майор рассчитывал, о чем и писал довольно откровенно своему другу Джеймсу Бэндинелу: «Уоррингтон пишет мне из Триполи, что Белло, вождь Судана, сообщил Клаппертону, будто Нигер впадает в Бенинский залив множеством рукавов. Это говорит в пользу моей гипотезы. Но я полагаю, кто-то должен спуститься по реке до побережья, прежде чем можно будет установить право на открытие».
Лэнг собирался отплыть с Мальты 10 мая, как только почувствует себя совсем здоровым. Уоррингтону он писал, что появится в Триполи «готовым… сразу отправиться в Гадамес». В действительности же майор предстал перед консулом уже 9 мая.
Но здесь его ждало первое разочарование (а сколько их еще будет потом!): о немедленном выходе из Триполи не могло быть и речи. Все было совсем не так просто, как представлялось по отчетам, которые получало министерство колоний. Прежде всего, требовалось получить разрешение паши Юсуфа Караманлы, а для этого немало понадобилось и времени, и усилий, и денег. Затем оказалось, что на предполагавшемся маршруте экспедиции — через гористую область Гарьян — поиска паши уже не первый год безуспешно пытаются справиться с восстанием местных берберов и что, следовательно, Лэнгу не удастся пройти к Гадамесу самым коротким путем, а придется двигаться кружной дорогой через Феццан. Наконец, приказ лорда Батерста гласил: майор Лэнг должен обязательно взять с собой в качестве проводника вождя одного из туарегских племен, Хатиту аг Худена. А поскольку тот еще не прибыл в Триполи и вообще не было известно, когда он появится, путешественнику оставалось только ждать.
Этот Хатита аг Худен был довольно любопытной личностью. Внимание к его особе со стороны министра колоний объяснялось просто: начиная с неудачной экспедиции Ритчи и Лайона Хатита служил проводником всем британским путешественникам в этой стране. В Лондоне о его возможностях были очень высокого мнения, да и сам он, несомненно, старательно набивал себе цену в глазах европейцев, хотя был главой небольшого и не слишком знатного племени, не располагавшего серьезной военной силой. Но к англичанам он, бесспорно, относился очень дружелюбно, и те платили ему взаимностью. А уважение и особенно подарки англичан в свою очередь поднимали престиж Хатиты в глазах кочевых соседей. Как бы то ни было, но на протяжении нескольких десятилетий вождь считался необходимым участником любого британского предприятия, связанного с географическим исследованием Судана с северной стороны. Беда только, что Лэнгу Хатита мог принести лишь небольшую пользу; доставить же майора в Томбукту, к официальной цели его миссии, он был бессилен. Хатита происходил из племени кель-аджер, а на главной дороге к Томбукту располагались кочевья арабов-шаамба и туарегов племен кель-ахаггар и кель-ифора, давних и непримиримых врагов кель-аджер. Впрочем, на Хатиту уповали больше Батерст и Уоррингтон. Сам он вовсе не предполагал сопровождать Лэцга до Томбукту, речь шла только о землях кель-аджер, и встретиться с путешественником он намерен был в Феццане. А добираться туда Лэнгу предлагалось самостоятельно.