Los orígenes de Reina se remontan a una ciudad romana: Regina Turdulorum, en el cruce de las dos calzadas que unía Córdoba con Mérida. Se supone que su fundación es cesariana o augustea, recibiendo organización política romana en tiempos de Vespasiano.

En aquellos tiempos fue una población populosa, casi de 4.000 habitantes, que disponían de agua potable que llegaba a través de un acueducto; sus calles eran amplias y porticadas, con alcantarillado subterráneo que desembocaba en los arroyos de San Blas y San Pedro.

Durante la época santiaguista fue cabeza de una poderosa Encomienda de la que dependían Ahillones, Berlanga, Casas de Reina, Disantos, Fuente del Arco, Trasierra y Valverde de Llerena.

En siglos posteriores el auge de Llerena absorbe la capitalidad de la Provincia Santiaguista.

La cerca que se conserva es de la época almohade -siglo XII-, con diversas restauraciones posteriores. Entre ellas las realizadas por el Maestre de la Orden de Santiago D. Alonso Cárdenas -siglo XV- y otras en los años 1515 y 1575.
La fortaleza fue abandonada entre los años 1604 y 1738, formándose poco a poco el pueblo actual. Las primeras casas empezaron a edificarse en la parte más baja de valle, los arrabales, donde se hallaban las bodegas.

En la antigua alcazaba mora se conserva una ermita del siglo XV cuyos orígenes pueden encontrarse en la época visigoda. Se conserva una peana de madera del siglo XIX.