La orden del Temple creó la Encomienda de Olivenza, dotándola de Castillo y de una Iglesia dedica a Santa María (1256) junto a la fuente de la Corna.
En 1306 Don Dinis de Portugal elevó la antigua aldea castellana a la categoría de villa e inició la reconstrucción de la fortificación templaria dándole forma de cuadrilátero. Ocupando una superficie de 18.600 metros cuadrados y un perímetro de 533 metros. Los muros de mampostería, de 3 metros de ancho y de 12 metros de altura. Colocando una puerta fortificada con dos torreones en cada cortina. Tras alguna restauración se conservan las cuatro puertas, si bien una perdió definitivamente sus torreones. Los ángulos están protegidos con torreones, siendo la del ángulo este una torre albarrana de 19 metros, a sus lados hay otras dos de 14 metros. Se conservan 10 torreones sin incluir la torre del reloj. Afonso IV, las completa en 1335 erigiendo en su interior el recinto del alcázar. Cada una de las cortinas del recinto es de diferente longitud. Este recinto ocupa una superficie de 1.450 metros cuadrados y un perímetro de 157 metros. La torre del reloj se construyó en 1460 sobre la torre de la esquina oeste de la ciudadela medieval. Juan II mandó hacer una cava inundable, que puede verse recuperada en el lado norte. En 1488 levantó la Torre del Homenaje, su sistema de comunicación se basa en 17 rampas para salvar sus 37 metros de altura, su base es de 18 metros de lado. Tiene 24 saeteras y esta dotada de matacanes.El fuerte crecimiento de Olivenza obligó a construir tres murallas más a lo largo de los años, apenas se conservan restos de las murallas segunda y tercera. El cuarto recinto es el sistema abaluartado.