During the second half of the 13th century, Gao and the surrounding region had grown into an important trading center and attracted the interest of the expanding Mali Empire. Mali conquered Gao towards the end of the 13th century; Gao would remain under Malian hegemony until the late 14th century. But as the Mali Empire started to disintegrate, the Songhai reasserted control of Gao. Songhai rulers subsequently took advantage of the weakened Mali Empire to expand Songhai rule. Under the rule of Sonni Ali, the Songhai surpassed the Malian Empire in area, wealth, and power, absorbing vast areas of the Mali Empire and reached its greatest extent. His son and successor, Sonni Bāru (1492–1493), was a less successful ruler of the empire, and as such was overthrown by Muhammad Ture (1493–1528; called Askia), one of his father's generals, who instituted political and economic reforms throughout the empire.
A series of plots and coups by Askia's successors forced the empire into a period of decline and instability. Askia's relatives attempted to govern the empire, but political chaos and several civil wars within the empire ensured the empire's continued decline, particularly during the brutal rule of Askia Ishaq I (1539–1549). However, the empire experienced a period of stability and a string of military successes during the reign of Askia Daoud (1549–1582/1583). Ahmad al-Mansur, the Moroccan sultan at the time, demanded tax revenues from the empire's salt mines. Askia Daoud responded by sending a large quantity of gold as gift in an attempt to appease the sultan. Askia Ishaq II (1588–1591) ascended to power in a long dynastic struggle following the death of Askia Daoud. He would be the last ruler of the empire. In 1590, al-Mansur took advantage of the recent civil strife in the empire and sent an army under the command of Judar Pasha to conquer the Songhai and to gain control of the Trans-Saharan trade routes. After the disastrous defeat at the Battle of Tondibi (1591), the Songhai Empire collapsed. The Dendi Kingdom succeeded the empire as the continuation of Songhai culture and society.
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 Sorko 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 crocodile and 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. The 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.
The camel-riding 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 gold, salt, slaves, kola nuts, leather, dates, and 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: