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. 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). 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 persons 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.