On the Yebala Peninsula on the coast of North Africa lies the ancient port and fortified town of Ceuta, with a population of nearly 72,000. Occupying 19.5 square kilometres, Ceuta is some 25 kilometres away from continental Europe across the Strait of Gibraltar and a mere ninety-minute ferry journey from the Spanish port of Algeciras, which can be seen from the promontory on a clear day. Some 250 kilometres to the east of Ceuta, on the Guelaia Peninsula jutting out into the Mediterranean, stands the town of Melilla with over 62,000 inhabitants. Melilla covers an area of 12.5 square kilometres and is eight hours by sea from Málaga on the Spanish Costa del Sol.

Archaeological evidence indicates that the settlements were first established in the third century BC, but an Arab presence can be traced from the eighth century AD. Occupied thereafter by a succession of caliphates and emirates owing to its economic and strategic importance, by the twelfth century Ceuta (or Sebta) had become one of the main Mediterranean ports. Melilla (or Mililia) was of lesser importance but attracted interest because of nearby salt deposits.

From a geographical perspective both towns are indisputably part of the continent of Africa. However, Melilla has been in Spanish hands since 1497, when it was seized by Pedro de Estopiñán, envoy of the Duke of Medina Sidonia, and is one of several fortresses or presidios which were established along the coast to prevent further invasions of the Spanish peninsula by the ‘Moors’ (the general term used to refer to the Arabs and Berbers from the south), who had finally been expelled five years earlier after a presence going back nearly eight centuries. Ceuta, which had been seized by Portugal in 1415, was formally transferred to Spain under the Treaty of Lisbon in 1668 following the ending of the union between Spain and Portugal in 1640. As part of Spain, with their own elected representatives in the national Parliament, these territories have well-established links with Europe, but following Spain's entry into the European Community in 1986 they became European by treaty: the majority of their citizens are Spanish and therefore now citizens of the European Union. They elect representatives to the European Parliament, and on the edge of both towns there are large hoardings proclaiming each to be a ‘Municipality of Europe’.