The empire was founded by the Songhay groups who inhabited the banks of the Niger river in the eastern part of the present-day state of Mali. As with the other empires in the region the origin of the kingdom is shrouded in myths and legends, although there seems to be some evidence that the original capita] of Gao was 100 km further south. The earliest record of Gao is from the eighth century when it is mentioned as one of the towns in contact with the Algerian city of Tahert. A tenth-century description describes the capital as composed of twin cities like the contemporary capital of Ghana and also describes the ruler as a Muslim.
Despite its strategic position on the trade routes Gao did not achieve imperial status until the fifteenth century when the empire of Mali was in decline. The first ruler to begin the expansion was Ali (1464-92) who conquered Timbuktu from the Berbers and Djenne from the disintegrating empire of Mali. Ali was followed by the most famous ruler of Gao, Askiya Muhammad, who usurped the throne from Ali's son. Askiya Muhammad consolidated the conquests of Ali and centralized the administration of the empire. He was a more convinced Muslim than Ali and made Islam the state religion as well as promoting Timbuktu as a centre of learning. In 1528 at the age of 85 Askia was deposed by his son and died ten years later in 1538. Following Askia there were a succession of short reigns between 1528 and 1591 which ended with the Moroccan invasion and the destruction of the Songhay Empire of Gao.
Fortunately the ancient capital of Gao has survived to provide some of the best examples of medieval architecture in West Africa. Three main groups of remains can be identified, Gao, Old Gao and Gao-Sane. It has been suggested that the twin-city configuration referred to in early accounts of Gao may be confirmed by the location of Gao-Sane 6 km east of the rest of the city. It is believed that Gao-Sane represents the Muslim quarter of the town due to its position facing the trade routes to North Africa. Old Gao probably represents the remains of the fourteenth-century city during the period when it was ruled by the empire of Mali. Excavations in Old Gao have revealed a large rectangular mosque (approximately 40 m wide) built of mud brick which was dated to 1325. In the centre of the west side is a deep circular mihrab (about 3 m in diameter) built of baked brick with a small doorway (a half-metre wide) on the north side. Behind the mihrab on the outside are three rectangular tombs one of which contains a headstone dated 1364. South of Old Gao is the main town which was the city of Askiya Muhhamad with its famous mausoleum contained within the courtyard of the Great Mosque. The Great Mosque is located within an area of cemeteries containing Kufic-inscribed tombstones dating from the early twelfth century. Some of the oldest tombstones were found within a subterranean vault made of baked brick similar to that used in the mihrab of the excavated mosque at Old Gao. The use of baked brick is significant in a context where they would have been very difficult to produce.
Undoubtedly the most important monument in Gao is the Great Mosque containing the tomb of Askiya Muhammad. The mosque consists of a large rectangular enclosure (45 by 50 m) with a sanctuary four bays deep. In the middle of the east wall of the sanctuary is a pair of niches one of which is the mihrab whilst the other contains a fixed minbar. The centre of the courtyard is occupied by the tomb of Askiya Muhammad, a huge pyramidical earth construction resting on a base measuring 14 by 18 m. The tomb consists of three steps or stages reaching a height of just over 10 m above ground level. A stair ramp made of split palms leads up the east side of the structure to reach the top. The appearance of the tomb is enhanced by the many toron, or stakes, made of acacia wood which project from each side. A description of the monument from 1852 mentioned another eastern tower which was in ruins at the time; this may have been the mihrab tower which also functioned as a minaret. It seems likely that with the collapse of the eastern mihrab/minaret tower stairs were cut into the tomb of Askiya Muhammad so that this could function as the place for the call to prayer. In view of Askiya Muhammad's strong attachment to Ibadi teachings it is thought that the architectural origins of this tomb may be round in various Ibadi zawiyas in the Mzab region of southern Algeria. The design of these three-tier constructions is said to derive ultimately from the minaret of the Great Mosque at Qairawan. One of the best examples is at Tidikelt in southern Algeria and consists of three superimposed stages each with a crenellated parapet. In addition to the orthodox Muslim influences on the design of the tomb, it should be noted that it also resembles the ancestral tumuli of the pre-Islamic Songhay past. This connection is reinforced by the toron projecting from the sides of the tomb.
In addition to Gao itself, there are a number of towns which contain monumental remains of the Songhay Empire. One of the best examples is the city of Tendirma in Mali built for Amar-Komdiago the brother of Askiya Muhammad in 1497. The construction of the city was carried out by Manding craftsmen under the direction of Ouahab Bari. Standing remains at Tendirma include the massive palace walls and the Great Mosque which is substantially unchanged since the Moroccan invasion of the sixteenth century. The mosque is built out of spherical mud bricks with the use of split palm and acacia wood for roof timbers. The most remarkable feature of the mosque is the mihrab tower which consists of a sloping cone with a flat surface on the side facing the mosque. Like the mausoleum of Askiya Muhammad the outer surface of the minaret is covered with projecting toron made of acacia wood. Other examples of Songhay imperial architecture can be seen in the mosques of Katsina and Birni in northern Nigeria. The Katsina minaret is particularly unusual and consists of a central square shaft with stair ramps ascending around the four sides. The minaret bears a striking similarity to the Malwiyya in Samarra although stylistically it is more closely related to the minaret of the Great Mosque in Qairawan.