Одновременно мне приятно было узнать, что мой предшественник в какой-то мере предупредил пожелания и нужды экспедиции, решив направить к Вам помощника, а также предоставить дополнительные средства. Я, со своей стороны, уполномочен довести до Вашего сведения, что правительство Ее величества одобряет Ваши намерения попытаться достичь Томбукту, и я надеюсь, что наградой за Ваше бесстрашие будет удача. Правительство Ее величества не преминет принять во внимание Ваше предложение о создании консульского агентства в Куке, однако этот вопрос связан с особыми трудностями и требует серьезных размышлений».
После волнующих и в некоторой степени обескураживающих событий в Томбукту восстановление контакта с Европой придало Барту новые силы, тем более что к этому времени вернулся его друг и покровитель шейх Эль-Баккаи. Однако последний, к великому сожалению Барта, не пожелал ускорить темп похода. Караван двигался черепашьим шагом, в обход множества рек и болот, теряя драгоценное время.
25 мая они наконец достигли Бамбы — самой северной точки на Нигере. Отсюда пестрое сборище двинулось в восточном направлении, к излучине реки около Бурема. Барт по-прежнему много работал днем, а вечерние часы досуга нередко проводил в дружеской беседе со своим покровителем и с местными туарегами. В этом ему очень пригодилось знание языков, которое он рассматривал как непременную предпосылку успешной исследовательской деятельности. Как и прежде, сильное впечатление на Барта производили туареги, их гордый нрав. При более близком знакомстве, однако, они были очень гостеприимными и обходительными людьми. Правда, поначалу требовалось войти к ним в доверие и устранить повышенную подозрительность, ибо туареги из племени тингеререф имели печальный опыт с Мунго Парком, который не задумываясь пускал в ход оружие. «Но когда они заметили, — писал Барт, — что я с некоторыми начинал оживленно беседовать, остальные убеждались, что я не принадлежу к категории диких зверей, ибо именно такое представление, кажется, сложилось у них обо всех европейцах после приема, устроенного им Мунго Парком».
Большие надежды Генрих Барт возлагал на Гао — древнюю столицу сонгаев. Если Томбукту получил известность как торговый и культурный центр, то Гао прославился как очаг крупных миграций и родина победоносных правителей.
Правда, от его былого величия мало что сохранилось. Дворцы лежали в руинах. Лишь остатки главной мечети и могила правителя и завоевателя аскии Мухаммеда еще напоминали о прежнем значении города. В период расцвета Гао достигал таких размеров, что пешеходу требовалось не менее трех часов, чтобы обойти его. Теперь в нем оставалось, самое большее, 400 жилищ. Три недели Барт посвятил изучению тех каменных свидетельств славного прошлого, которые ему посчастливилось здесь увидеть. В то же время он старался как можно больше общаться с жителями, расширяя словарь сонгайского языка и совершенствуя свои познания в области этнографии и истории.