По легендам, собранным Бубу Хама, сонгаи жили в Катука долго (по Абдул Закиру, 150 лет), пока им не пришлось отступить на юг перед племенами хауса, предводительствуемыми царем сарки Баяджидда. Это произошло будто бы в те времена, когда народом Сонгай правила королева Тун-тун, или Тунтума. Сонгаи переселились из Катука на 400 км южнее, остановившись в долине Нигера около Джеббы. Впоследствии они двинулись оттуда вдоль реки на север и основали маленькое государство в Бусе. Оттуда, согласно Хама, странствия сонгаев продолжились далее на север вплоть до Кебби,[82] где они основали свою столицу Гунгу.

По словам Бубу Хама, «йеменские принцы» были не из Йемена, а из Эфиопии и не светло-, а темнокожие, и пришли они именно в Гунгу, или Вейза-Гунгу, что означает «женский остров». Название это возникло оттого, что правила в Гунгу женщина, сонгайская царица Вейза. С прибытием «йеменцев» в правящую династию сонгаев влилась новая кровь: Вейза вышла замуж за одного из чужеземцев. Ее братья, принадлежавшие к клану Сонинке, отнеслись неодобрительно к появлению нового рода властителей и ушли из Вейза-Гунгу, правда, не очень далеко. Со своими сторонниками они основали торговый центр под названием Ар-Гунгу, то есть «мужской остров». Однако уход братьев Вейзы не принес покоя в Сонгай. Напротив между кланом Дья (или потомками Вейзы и Дья эль-Йемена с их сторонниками) и потомками братьев Вейзы вражда была столь острой, что клан Дья решил уйти на север по Нигеру в Бенти-Гунги; это название в арабских источниках превратилось в Куки.

Согласно сведениям Бубу Хама, Куки находилась примерно в 500 км к северу от Кебби. Вместе с кланом Дья туда переселилась значительная часть племени сорко.[83]

По сведениям Хама, странствия сонгаев-дья не кончились в Куки, они продвинулись еще на добрых 100 км вверх по течению Нигера. У впадения уэда Тилемси в Нигер они основали город Гангабер[84] еще до того, как, наконец, остановились в Гаво, или Гао. Но и в Гао — что означает «большой лагерь» — они не сразу осели окончательно.

Сначала они стали лагерем на правом берегу в Гао-Койма, а оттуда перешли на другой берег в Гао-Сане. Переселение на левый берег было связано с быстрым развитием Гао-Сане. Оно было вызвано многими факторами, в частности оживлением в Сане торговли, в которой принимали участие арабы, сонгаи, берберы и сонинке из Ар-Гунгу. Властвовавшие в Тадмекке Альморавиды[85] послали своих представителей в Сане, что тоже подняло значимость этого берега реки.

По данным Бубу Хама, в те времена в Гао-Сане правил Дья Косой-Мослем-Дам, первый царь Гао, исповедовавший ислам. Причиной его перехода в ислам было, видимо, как и у других правителей Ганы, представление, что мусульманство будет способствовать торговым связям с берберами, приходившими сюда с севера. О торговых и культурных связях Гао свидетельствуют найденные в Гао-Сане[86] надгробия царствовавших в XII в. царей. Надписи на них сделаны куфическим письмом и стилем, свойственным арабской Испании того времени. Сами надгробия сделаны из привозного испанского мрамора. Таким образом, связи царей Гао с исламским миром существовали.

Пока что историки не могут реконструировать список властителей Гао XII в., хроники и надгробия содержат разные имена. По устной традиции, до Дья Косоя в Сонгай господствовало 14 царей династии Дья. Все они были анимистами. Династия Дья владела, как считается, торговым центром примерно 600 лет, до паломничества (хаджжа) мансы Мусы в Мекку. Считается, что династия сонни, или ши, началась с Али Колена, сына Дья Ассибоя, и восемнадцатым царем этой династии был ши Али Бер, настоящий основатель Сонгайской империи.

Развитие Гао в XII–XIII вв. шло, видимо, довольно спокойно, поскольку об этом времени не осталось значительных сведений ни в устной традиции, ни, в письменных источниках. Мали, захватившее после Ганы гегемонию в Западном Судане, стремилось включить в круг своей власти процветающие торговые центры, чтобы получить свою долю доходов от караванной торговли. По некоторым данным, Гао начало платить дань Мали в XIII в. Обычно же считается, что город попал в круг подвластных Мали в связи с хаджжем мансы Мусы. Такая хронология прослеживается как в арабских хрониках, так и в большей части устной традиции. По обычаю тех времен, став вассалом мансы Мусы, Дья Ассибой должен был отдать своего сына в качестве заложника малийскому двору.

По некоторым версиям, Дья Ассибой обманул малийского государя, отдав ему не своего сына, а детей одного из своих военачальников. Обычно же Али Колена и Сулеймана Нара, живших при малийском дворе, считают сыновьями Дья Ассибоя. По некоторым сведениям, они были от разных матерей, бывших сестрами. Дья Ассибой женился сначала на Фати, которая никак не могла родить ему сына и сама посоветовала, чтобы царь взял себе в жены ее сестру Омму. Тот так и сделал, хотя женитьба на сестрах была запрещена мусульманским законом. Сестры одновременно забеременели, и каждая родила сына в одну и ту же ночь. По местному обычаю, детей, родившихся ночью, обмывали первый раз с наступлением утра, и поскольку сына, рожденного Оммой — его назвали Али Колен, — мыли первым, его и стали считать старшим.

Оба они, Сулейман Нар и Али Колен, будучи заложниками, проявляли себя как умелые охотники и воины, особенно последний, который в качестве военачальника принимал участие во многих военных экспедициях и грабительских набегах.[87]

Рассказывается, что в каждом походе он выбирал новый маршрут, чтобы как можно лучше изучить местность. Во время походов он устраивал вдоль троп склады продовольствия и оружия, так как решил при удобном случае бежать от малийского двора и помочь Гао обрести независимость. При смене правителя он счел, что такой случай наступил, и пустился с братом в долгий путь. Когда малийский манса Маган узнал о бегстве заложников, он отправил в погоню отряд воинов. Но военное искусство Али Колена и его знание местности сделали свое дело. В конце концов царевичи вернулись на родину.

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