De muren die Tarifa omringen zijn in essentie het resultaat van een proces bestaande uit verschillende fasen van bouwen en restaureren.

In hoofdzaak kan m'n twee fasen onderscheiden. De eerste stamt uit de tijd van de Islamitische bezetting die de oude stad (medina) includeert, gedurende dewelke de zuidelijke stadszone werd afgesloten. De restanten van deze periode kunnen nog steeds gezien worden op de kliffen gelegen in de Straat. De Almedinadeur is het enige wat overblijft van deze periode.

Na de verovering door de Katholieken, breidde de medina zich verder uit tot aan de huidige muren die tussen de 15de en 16de eeuw gebouwd werden. Van dit tweede defensiesysteem blijft enkel één poort bewaard: de Puerta de Jerez, aan de noordelijke zijde van de stad.