In ancient times there were several different groups of people that collectively formed the Songhai identity. Among the first people to settle in the region of Gao were the Songhai's people, who established small settlements on the banks of the
Niger River. The Sorko fashioned boats and canoes from the wood of the
cailcedrat tree and fished and hunted from their boats and provided water-borne transport for goods and people. Another group of people that moved into the area to exploit the Niger's resources were the Gow people. The Gow were hunters and specialized in hunting river animals such as
hippopotamus. The other group of people known to have inhabited the area were the Do people. They were farmers who raised crops in the fertile lands bordering the river. Sometime before the 10th century, these early settlers were subjugated by more powerful, horse-riding Songhai speakers, who established control over the area. All these groups of people gradually began to speak the same language and they and their country eventually became known as the Songhai.
The earliest dynasty of kings is obscure and most of the information about this dynasty comes from an ancient cemetery near a village called
Saney, close to Gao. Inscriptions on a few of the tombstones in the cemetery indicate that this dynasty ruled in the late 11th and early 12th centuries and that the rulers from this dynasty bore the title of
malik. Other tombstones mention a second dynasty, whose rulers bore the title zuwa. There is only myth and legend to describe zuwa origins.
Tarikh al-Sudan (the History of the Sudan), written in Arabic around 1655, provides an early history of the Songhai as handed down through oral tradition. The chronicle reports that the legendary founder of the
Za or the
Zuwa dynasty was called Za Alayaman, who originally came from
Yemen and settled in the town of Kukiya.
 What happened to the Zuwa rulers is not recorded.
Sanhaja tribes were among the early people of the Niger bend region. They were locally known as the
Tuareg. These tribes rode out of the great
Sahara Desert and established trading settlements near the Niger. As time passed,
North African traders crossed the Sahara and joined the Tuaregs in their Niger bend settlements. They all conducted business with the people living near the river. As trade in the region increased, the Songhai chiefs took control of the profitable commerce around what was to later become Gao. Between 750 and 950, as the
Ghana Empire prospered as the "land of gold" far to the west, the trading centre at Gao became an increasingly important terminus for trade across the Sahara. The trade goods included
ivory. And by the 10th century, the Songhai chiefs had established Gao as a small kingdom, taking control of the people living along the trade routes. At around 1300, Gao had become so prosperous that it attracted the attention of the
Mali Empire and its rulers. Gao was subsequently conquered by them and Mali profited from Gao's trade and collected taxes from its kings until about the 1430s. Troubles in the Mali homelands made it impossible to maintain control of Gao.
Ibn Battuta visited Gao in 1353 when the town was a part of the Mali Empire. He arrived by boat from Timbuktu on his return journey from visiting the capital of the empire:
Then I travelled to the town of Kawkaw, which is a great town on the Nīl [Niger], one of the finest, biggest, and most fertile cities of the Sūdān. There is much rice there, and milk, and chickens, and fish, and the cucumber, which has no like. Its people conduct their buying and selling with cowries, like the people of Mālī.
Following the death of
Mansa Sulayman in 1360, disputes over the succession weakened the Mali Empire. Furthermore, the ruinous reign of
Mari Djata II left the empire in bad financial shape, but the empire itself passed intact to
Musa II. However, real power in the empire was in the hands of Mari Djata, Musa's kankoro-sigui. He put down a Tuareg rebellion in
Takedda and attempted to quell the Songhai rebellion in Gao. While he was successful in Takedda, he did not manage to re-subjugate Gao, and so the Songhai effectively retained their independence.
 During his reign, Sonni Ali would be the one to expand the small kingdom of Gao into an enormous empire.
Sonni Ali was the first king of the Songhai Empire and the 15th ruler of the Sonni dynasty. He worked his hardest to get the Songhai empire out of its rocky start. The Muslim leaders of Timbuktu asked him to drive out the invaders. Once Sunni Ali drove them out, he took this chance and took over Timbuktu. Soon, he had almost all the trading cities along the Niger River.