Las tierras llanas de Olivenza condicionaron el surgimiento tardío de un núcleo de población. No obstante, el ser humano dejó aquí restos neolíticos, romanos, visigodos y árabes.
En 1230 Alfonso IX de León conquista Badajoz. Los árabes se repliegan hacia el sur, consolidando los reyes cristianos estas posiciones y entregando Alconchel a la orden templaria. Desde ahí, esta orden ampliará sus dominios, poblando las tierras de Olivenza, construyendo iglesia y castillo. Esta encomienda solo duró 28 años, hasta 1278, porque Badajoz acusó a los templarios de haber poblado en sus tierras, siendo revertidas a su concejo.
Aprovechando las guerras civiles en Castilla y León, tras la muerte de Sancho IV, el rey D. Dinis acordó (Alcañices, 1297) con la reina regente, Dª. Mª de Molina, la entrega de tierras fronterizas a Portugal (entre ellas Olivenza) a cambio de no apoyar a sus enemigos. El rey D. Dinis, ayudado por la Orden de Avis, comenzó su primera muralla en 1306. Su hijo, Alfonso IV, levantó alcázar y torre del homenaje en 1332. En 1488 D. Juan II mejora dicha torre. A partir de ahí Olivenza sería portuguesa, salvo pequeños interregnos por causas bélicas, hasta 1801. Su carácter en todo este tiempo fue de plaza militar fronteriza. La mayores realizaciones son del reinado de D. Manuel (S. XVI): Magdalena, Casa de Misericordia, Puente Ayuda. En la guerra de restauración de la corona portuguesa fue tomada por las tropas españolas en 1657 y devuelta en 1668 por el Tratado de Lisboa que puso fin a esa guerra.
En 1801 Napoleón, aliado de España, manda invadir Portugal, aliada de Inglaterra. Tras breve campaña (y a espaldas de Napoleón) se firma el Tratado de Badajoz, de junio de ese año, por el que se devuelven las plazas tomadas, salvo Olivenza, fijándose la frontera en el Guadiana.
La Olivenza española se ha constituido en cabecera de una importante comarca, sabiendo conservar su extraordinario legado monumental y cultural. Se convierte así en un enclave donde se funden las culturas portuguesa y española. Su patrimonio monumental fue declarado «Conjunto de interés histórico-artístico» en 1964. Desde 2019, forma parte de la Asociación de los Pueblos Más Bonitos de España.