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.
La primera piedra la puso Pero Lourenço de Rego en 1306. A partir de 1309 la Orden de Avis dio a las obras el impulso definitivo con las rentas de la iglesia de Santa María. 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. Se conservan dos de ellas: Alconchel y Los Ángeles.
En 1334 el rey D. Alfonso IV inicia la construcción de ese elemento característico del urbanismo musulmán que es la alcazaba, recinto amurallado dentro de las murallas. El ángulo E de la ciudadela se cerró interiormente con dos cortinas. En la intersección de las mismas se levantó una torre.
Castillo Pero será D. João II, en 1488, quien otorgue una nueva fisonomía al conjunto. A pesar de los pactos de desarme suscritos con los Reyes Católicos, el Príncipe Perfeito alza en Olivenza la más alta torre de toda la frontera: 37 m. de altura. Construida en mamposteria reforzada por sillares en los ángulos, se accede a la terraza del Homenaje a través de 17 rampas. Una barbacana, a cuyo pie se abría un foso inundable, rodeaba por completo la alcazaba oliventina. De ella nos dejó en 1509 cumplido testimonio gráfico el tracista Duarte d´Armas en su famoso Livro das Fortalezas.
En el interior del alcázar, y en la anexa Panadería del rey (s. XVIII) se encuentra el Museo Etnográfico.