Muralla
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.
Estructura y componentes
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 hasta los adarves. Se conservan dos de ellas: Alconchel y Los Ángeles, de torres semicirculares.
La Puerta de la Gracia sólo mantiene el arco, habiendo perdido sus torres de base cuadrada. La antigua puerta de San Sebastián, en el lado norte, se derribó por proposición de 25 de enero de 1854, ante el Ayuntamiento Pleno, dado su estado de ruina inminente. Desde 2006 se encuentra reconstruida.