There is local evidence that Stone Age cave-dwellers used rocks to form living chambers. Roman ruins also exist in the area.
Arcos became an independent Moorish taifa in 1011 during the protracted collapse of the Umayyad Caliphate of Córdoba. Arcos was associated with the Jerez by 'Abdun ibn Muhammad who ruled from c. 1029/1030 to 1053. The region was overtaken by the Almoravid dynasty in 1091. From 1145 to 1147 the region of Arcos and Jerez was briefly a taifa under dependency of Granada, led by Abu'l-Qasim Ahyal.
The town was a bulwark of Christianity after Alfonso the Wise of Castile (1252–1284) expelled the Moors. He constructed a Gothic cathedral which remains on its high ridge.
It is famed for its ten bells, which tolled throughout the war with the Moors. Several Moorish banners were taken in the nearby battle of Zahara and have been on display in a church in Arcos since 1483
