17 июня 1825 года Ленг сел на корабль на Мальте и отплыл в Триполи. Шотландец приступил к своей миссии очень уверенный в себе, ибо во время подготовки к путешествию в июле женился на дочери британского консула. Через два дня после этого события он отправился в путь через Сахару. До оазиса Туата вместе с ним ехал Хатита, вождь Тарги, или Туарег . Пройдя от Триполи до северной окраины Феццана, экспедиция двинулась оттуда на запад новым для европейцев путем через оазисы Гадамес и Айн-Салах. Ведя маршрутную съемку и научные наблюдения, Ленг не переставал размышлять о проблеме Нигера. В Гадамесе, где он прожил два месяца, им были написаны и отосланы в Триполи Беглые заметки о течении и окончании великой реки Нигер , свидетельствующие об изменении его взглядов по этому вопросу: теперь он выдвинул предположение о том, что нижним течением Нигера может являться река Вольта, впадающая в Гвинейский залив на Золотом Береге. В октябре Ленг покинул этот оазис и добрался до Айн-Салаха одного из группы оазисов Тидикельт в Алжирской Сахаре. Выяснилось, что оазис этот расположен гораздо западнее, чем считалось раньше. Прожив там с ноября 1825 года до января 1826 года, майор достиг затем оазисов Туат; оттуда он предполагал направиться в Томбукту, объехать озеро Дженне или Дебои, посетить область Мелли и по течению Джолибы спуститься до ее устья. Затем он намеревался вернуться обратно, дойти до Сокото, посетить озеро Чад и постараться выйти к Нилу. Однако когда караван, к которому присоединился Ленг, покинул Туат, на него напали. По словам одних, это были туареги, по словам других, берабиши племя, жившее неподалеку от Джолибы. Дознались, что Ленг -христианин, рассказывает француз Кайе, собравший эти сведения в Томбукту, и обошлись с ним чрезвычайно жестоко. Его били палкой, пока не решили, что он мертв. Другой христианин, умерший, как мне говорили, под ударами, был, наверное, один из слуг майора. Мавры из каравана Ленга подобрали его и постарались привести в чувство. Когда он пришел в себя, его посадили на верблюда. Однако Ленга пришлось привязать к седлу: он был так слаб, что не мог держаться. Разбойники не оставили ему почти ничего: большая часть его товаров была разграблена . Итак, один из европейских участников экспедиции был убит, сам Ленг тяжело ранен. Вскоре эпидемия дизентерии унесла в могилу всех остальных его спутников. Несмотря ни на что, Ленгу удалось завершить этот труднейший и опаснейший переход через Сахару и вступить 13 августа 1826 году в город своей мечты Томбукту. Очевидно, он был первым европейцем после Бенедетто Деи (1469 год), вошедшим туда добровольно.
В Томбукту Ленг стал постепенно оправляться от ран. Выздоровление шло медленно, но благодаря рекомендательным письмам, привезенным из Триполи, и самоотверженным заботам своего хозяина, родом триполитанца, больной не подвергался преследованиям со стороны местных жителей. Судя по рассказу одного старика, слышанному Кайе, Ленг, как это ни странно, продолжал носить европейское платье и заявлял, будто послан своим господином, королем Англии, в Томбукту, чтобы описать все чудеса этого города. По-видимому, добавляет французский путешественник, Ленг на глазах у всех снимал план города, потому что этот же мавр, по-своему выразительно и наивно, рассказывал мне, что Ленг списал город и все, в нем находившееся . Осмотрев в подробностях Томбукту, Ленг, у которого были особые причины опасаться туарегов, ночью отправился в Кабру, чтобы полюбоваться на Джолибу (Нигер). Майор не хотел возвращаться в Европу через Великую пустыню, но горел желанием побывать в Дженне и Сего, а затем выйти к французским поселениям на Сенегале. В письме британскому консулу в Триполи, датированном 21 сентября 1826 года, Ленг сообщил, что намеревается двинуться к Сегу в верхнем течении Нигера. Это было единственное письмо, написанное им из Томбукту, и последнее, которое вообще было от него получено. Но не успел он сказать и нескольких слов об этом плане сбежавшимся посмотреть на него фульте, как те заявили, что не позволят назареянину ступить на их землю, а если он посмеет это сделать, они заставят его горько раскаяться. Поэтому Ленг был вынужден выбрать дорогу на Араван, где он надеялся примкнуть к какому-нибудь каравану купцов-мавров, которые возят соль в Сансандинг. Однако через пять дней после того как он выехал из Томбукту, к его каравану присоединился фанатик-магометанин, шейх Хамед-Ульд-Хабиб, вождь племени зауат. Под предлогом, будто Ленг без разрешения вступил на территорию этого племени, его тотчас же схватили. Ему предложили перейти в магометанство. Майор отказался и заявил, что предпочитает смерть отступничеству. Тут же на месте шейх и его приспешники обсудили, какой казни подвергнуть свою жертву, и Ленг был задушен двумя рабами, а тело его брошено в пустыне. Еще раньше в своих письмах Ленг с резким осуждением отзывался о кровавых подвигах своего предшественника Мунго Парка. Как неосторожно, как бездумно, могу даже сказать, как эгоистично, было со стороны Парка пытаться совершать открытия в этой стране ценой крови ее обитателей, как неоправданно было такое поведение!.. Боюсь, что после выезда из Томбукту у меня будет много неприятностей .
Все экспедиционные материалы пропали, и поэтому второе путешествие Ленга, отличавшееся гораздо большим размахом, чем первое, имело меньшее научное значение. Все же благодаря его письмам с дороги оно тоже прошло не без пользы для географии. Только позднее историки географических открытий стали воздавать Ленгу должное. А в 1930 году, через 100 с лишним лет после его смерти, в Томбукту, на стене дома, где он жил, была укреплена мемориальная доска с надписью: Майору Александру Гордону Ленгу, 2-го Вест-Индского полка, первому европейцу, достигшему Томбукту.