The city has a long history. It was founded by phoenicians. Named Iulia Traducta by the Romans in the First Century. In 711, Arab from the North of Africa invaded the city and renamed it Al-Yazirat al-Hadra (green island). In 1344 the city was conquered by Alfonso XI of Castile but it was reconquered by moors in 1369, ten years before Algeciras was destroyed.