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.
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 chronicles do not, in general, acknowledge their sources. Their accounts for the earlier periods are almost certainly based on oral tradition and for events before the second half of the 15th century they are likely to be less reliable. For these earlier periods the two chronicles sometimes provide conflicting information.
The earliest mention of Gao is by al-Khwārizmī who wrote in the first half of the 9th century. In the 9th century Gao was already an important regional power. Al-Yaqubi wrote in his Tarikh in around 872:
There is the kingdom of the Kawkaw, which is the greatest of the realms of the Sūdān, the most important and most powerful. All the kingdoms obey its king. Al-Kawkaw is the name of the town. Besides this there are a number of kingdoms of which the rulers pay allegiance to him and acknowledge his sovereignty, although they are kings in their own lands.
Ibn al-Faqih (writing c. 903) mentions a caravan route from Egypt to ancient Ghana via Kawkaw. but Ibn Hawqal (writing c. 988) states that the old route from Egypt to the Sudan was abandoned in the reign of the Egyptian ruler Ibn Tulun (ruled 868-884) as some of the caravans were attacked by bandits while others were overwhelmed by the wind-blown sand. The more direct route was replaced by one that went to Sijilmasa before heading south across the Sahara.