The old part of Mahdia corresponds to the Roman city called Aphrodisium and, later, called Africa (a name perhaps derived from the older name), or Cape Africa. The Catholic Church's list of titular sees includes a no longer residential bishopric called Africa and, since there is no record of an episcopal see in Roman times called by either of these names (nor by that of Alipota, another Roman town that Charles Tissot suggested tentatively might be represented by present-day Mehdia), it is supposed that the episcopal see of Africa was established when the city was held by the Kingdom of Sicily (1147–1160) and when Pope Eugene III consecrated a bishop for it in 1148. An inventory of movable property of the church of Africa (inventarium thesauri Africani) exists in an archive of the Cappella Palatina of Palermo in Sicily.
Robert Favreau identified Mahdia instead with ancient Ruspae or Ruspe, which is more commonly taken to have been at Henchir Sbia (or just Sbia), north of Mahdia, or at the ruins known as Ksour Siad. The most illustrious bishop of this see was Fulgentius of Ruspe. The Catholic Church's list of titular sees, which identifies the see of Africa as Mahdia, identifies Ruspe/Ruspae as Henchir Sbia.
The Mahdia shipwreck – a sunken ship found off Mahdia's shore, containing Greek art treasures – is dated to about 80 BC, the early part of Roman rule in this region.
Muslim Mahdia was founded by the Fatimids under the Caliph Abdallah al-Mahdi in 921 and made the capital of Ifriqiya. It was chosen as the capital because of its proximity to the sea, and the promontory on which an important military settlement had been since the time of the Phoenicians.
In 1087 the town was attacked by raiding ships from Genoa and Pisa who burned the Muslim fleet in the harbor. The attack played a critical role in Christians' seizure of control of the Western Mediterranean, which allowed the First Crusade to be supplied by sea. The Zirid dynasty had its residence here in the 11th century, but was brought to an end by the Norman conquest of the city in 1148. In 1160 the city came under Almohad rule.
The role of the capital was taken over by Tunis in the 12th century during the Almohad era, which it remained during the Hafsid Dynasty. Some buildings still exist from the 10th and 11th centuries, such as the Great Mosque and the Casbah, which have helped make the city an important tourist attraction. Later the city was subject to many raids. In 1390 it was the target of the Mahdian Crusade, when a French army laid siege to the city but failed to take it.
The city was captured by the Spaniards in 1550. A Spanish garrison remained there until 1553. Charles V then offered the charge of the town to the Order of Saint John who ruled Malta but they refused it deeming it too expensive. The emperor ordered the Viceroy of Sicily, Juan de Vega, to dismantle Mahdia despite it being a strategically important stronghold. The demolition tasks were carried out by Hernando de Acuña. Shortly after Mahdia was reoccupied by the Ottomans, but only to live by fishing and oil-works, and the town lost its logistic and commercial importance. It remained under Turkish rule until the 19th century.