The Gao Empire precedes that of the Songhai Empire in the region of the Middle Niger. It owes its name to the town of Gao located at the eastern Niger bend. In the ninth century CE, it was considered to be the most powerful West African kingdom.

For much of its history Gao was an important commercial centre involved in the trans-Saharan trade. In the 9th century external Arabic writers described Gao as an important regional power and by the end of the 10th century, the local ruler was said to be a Muslim. Towards the end of the 13th century Gao became part of the Mali Empire, but in first half of the 15th century the town regained its independence and with the conquests of Sunni Ali (ruled 1464–1492) it became the capital of the Songhai Empire. The Empire collapsed after the Moroccan invasion in 1591 and the invaders chose to make Timbuktu their capital. By the time of Heinrich Barth's visit in 1854, Gao had declined to become an impoverished village with 300 huts constructed from matting. In 2009, the urban commune had a population of 86,633.

Apart from some Arabic epitaphs on tombstones discovered in 1939 at the cemetery of Gao-Saney (6 km to the east of the city) there are no surviving indigenous written records that date from before the middle of the 17th century. Our knowledge of the early history of the town relies on the writings of external Arabic geographers living in Morocco, Egypt and Andalusia, who never visited the region. These authors referred to the town as Kawkaw or Kuku. The two key 17th century chronicles, the Tarikh al-Sudan and the Tarikh al-Fattash, provide information on the town at the time of the Songhai Empire but they contain only vague indications on the time before.

The archaeological evidence suggests that there were two settlements on the eastern bank of the Niger: Gao Ancien situated within the modern town, to the east of the Tomb of Askia, and the archaeological site of Gao-Saney (Sané in French) situated around 4 km to the east. The bed of the Wadi Gangaber passes to the south of the Gao-Saney occupation mound (tell) but to the north of Gao Ancien. The imported pottery and glass recovered from Gao-Saney suggest that the site was occupied between the 8th and 12th centuries.

The discovery of the tombstones of Gao-Saney in 1939 has provided the historians of the Gao Empire with new evidence. The three great Muslim rulers belonging the Zaghe dynasty who died successively in 1100, 1110 and 1120 can be identified with the kings of the Zuwa dynasty. The Islamization of the dynasty took therefore not place at the beginning but at the end of the eleventh century in the time of the Almoravids. The role of the Almoravids in this process has been hotly debated. Earlier the kings of Gao-Saney were considered to be offshoots of the Almoravids (John Hunwick, 1980), but it has recently been argued that they were converted rulers of a great African dynasty, possibly originating from ancient Ghana (Dierk Lange, 2004).