Mandado construir por el califa Abderramán III concluido en el 960, un año antes de su muerte, es junto con la alcazaba de Mérida, el castillo español visitable más antiguo de España. Es de planta trapezoidal con un conjunto de torres poco salientes y lienzos de muralla cortos, al clásico estilo califal de inspiración bizantina. Se encuentra intacto en su trazado original salvo en el frente Este, al que se le añadió un torreón octogonal llamado de Guzmán El Bueno, probablemente del siglo XII. Posteriormente se le añade el muro que conecta con la torre albarrana. La puerta principal en el lado occidental.

En el momento de la conquista de Tarifa por Sancho IV, en 1292, la cerca de la ciudad era muy reducida; iniciándose a continuación del muro Este del castillo y quedando oculta entre las construcciones que, con el paso del tiempo, se iban adosando a ella. Al crecer la población con la llegada de los cristianos, se construyó una nueva cerca con cuatro caras exteriores y cuatro torres cuadradas en sus ángulos. De la cerca, que aún posee grandes trechos en pie, se conservan la Puerta de Jerez (siglo X), y la del Retiro.