The area of the city has been populated since prehistory, and the earliest remains belong to Neanderthal populations from the Paleolithic.
Due to its strategic position it was an important port under the Phoenicians, and was the site of the relevant Roman port of Portus Albus ("White Port"), with two near cities called Caetaria (most likely Iberians) and Iulia Transducta (Tarifa), founded by the Romans themselves.
After being destroyed by the Germanic Barbarians and their Vandal allies, the city was founded again in April 711 by the invading Moors, as the first city created by the Arabson the occupied Spanish soil. It enjoyed a brief period of independence as a taifastate from 1035-1058. It was named al-Jazirah al-Khadra' ("Green Island") after the offshore Isla Verde; the modern name is derived from this original Arabic name (compare also Algiers and Al Jazeera).
In 1278, Algeciras was besieged by the forces of the Kingdom of Castile under the command of Alfonso X of Castile and his son, Sancho IV. This siege was the first of a series of attempts to take the city and ended in failure for the Castilian forces. An armada sent by Castile was also annihilated whilst trying to blockade the city's harbor.
After many centuries of Muslim rule, the tide of the reconquista arrived at Algeciras. In July 1309 Ferdinand IV of Castile laid siege to Algeciras as well as Gibraltar. The latter fell into Christian hands, but Muslim Algeciras held on for the following three decades, until Alfonso XI of Castile resumed its siege. Juan Nunez de Lara, Juan Manuel, Pedro Fernández de Castro, Juan Alfonso de la Cerda, lord of Gibraleón all participated in the siege, as did knights from France, England and Germany, and even King Philip III of Navarre, king consort of Navarra, who came accompanied by 100 horsemen and 300 infantry. In March 1344, after several years of siege, Algeciras surrendered.
The city was, however, retaken by the Moors in
