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