El rey D. Dinis, mandó en 1306 construir la primera muralla. La piedra fundacional la puso Pero Lourenço do Rego y a partir de 1309 la Orden de Avis dio a las obras el impulso definitivo.
El Casco antiguo de Olivenza reproduce la estructura original de las bastides: un cuadrilátero con cuatro puertas, cortado por dos calles perpendiculares que se cruzan en el centro. Todo el conjunto, en sentido E/O, se proyecta emblemáticamente contra la frontera.
Con muros de 3 m. de ancho y 12 de altura, el conjunto tenía un total de 14 torres; albarrana la del ángulo más expuesto. En cada cortina se abría una puerta, fortificada con torreones macizos. Hoy en día existe el proyecto de reconstrucción, estando levantada la base de su torre izquierda.