La situación estratégica del cerro del Castillo y la riqueza minera de la zona le confiere unas cualidades muy apropiadas para la defensa en tiempos difíciles. Esto hace que su poblamiento se remonte a etapas tan tempranas como la Edad del Bronce.
Las siguientes noticias que encontramos sobre el poblamiento en el mencionado cerro, las ofrece Plinio en su “Historia Natural”, en la que cita el oppidum de Regina como uno de los poblados fortificados situados en la Beturia túrdula. Ocupaba la parte amesetada del cerro mirando hacia el sur (Sierra Morena), por donde subía el camino de acceso a la cima, conservándose aún algunos tramos excavados en la roca. En la cima o en las laderas pueden observarse restos de las antiguas construcciones: aljibes, sillares de granito e innumerables restos cerámicos, reaprovechados después en la construcción de la alcazaba.
En época túrdula y romana permitía la vigilancia de un extenso territorio y el control de los pasos que cruzaban Sierra Morena, así como las calzadas que unían Emérita (Mérida) con Corduba (Córdoba) y con Híspalis (Sevilla) a través de Astigis (Écija).
A mediados del siglo I la paz y las incomodidades de las alturas potenciará la fundación de la conocida hoy día como la ciudad de Regina. Esto hace que los reginenses abandonen progresivamente el oppidum. Pronto se convirtió en una ciudad floreciente de 3000 o 4000 habitantes, en la que destaca el teatro, el foro o las cloacas, en excelente estado de conservación.
En la etapa visigoda, volvemos a encontrar referencias históricas sobre Regina, que aparece mencionada en las actas del II Concilio Hispalense en el siglo VII. De esta época, aún podemos observar los capiteles y fustes de columna que se conservan en la ermita de Ntra. Sra. de las Nieves, situada en recinto de la fortaleza.
La ocupación árabe empuja de nuevo a sus habitantes a la sierra buscando protección. Aprovechando los restos del antiguo oppidum, se construye una primera fortificación en la parte más elevada del terreno, referido luego en las fuentes medievales como el “Castillo Viejo”. De él, apenas se conservan los cimientos y un aljibe cuadrado, ya que volvió a reutilizarse y transformarse con posterioridad. Alfonso IX toma la fortaleza en 1185 matando a muchos de sus defensores y haciendo cautivo al resto. Al poco tiempo es recuperada por los almohades, y tras la batalla de Alarcos (1195), Yacub ben Yusuf manda fortificar todas las alcazabas al sur de Toledo, construyendo en Reina una impresionante alcazaba y una cerca amurallada para proteger a la población. Se construyeron utilizando la técnica del tapial (la tabiya musulmana) a base de tierra y cal compactada con golpes de pisones o mazas. Las murallas han sido restauradas recientemente, de manera que podemos hacernos una idea bastante acertada del perímetro y las dimensiones del recinto amurallado. De la etapa islámica, además se conserva el acceso original a la fortaleza, situado en el flanco norte. La puerta original, hoy reconstruida, mantiene la estructura en recodo característica de las fortificaciones islámicas, protegida por una torre albarrana.
En 1246 es entregada, sin lucha, a Fernando III el Santo que se encontraba en la conquista de Sevilla, que la dona a la Orden de Santiago para su protección y administración. En el privilegio de donación señala los mismos límites que tuvo “en tiempos de moros” con lo que se convierte en cabecera de una de las encomiendas más extensas de la Provincia de León de la Orden de Santiago, con unos 1500 kms. cuadrados.
La Orden reforma y adapta la fortaleza atendiendo a sus necesidades, transformando la antigua entrada en recodo, construyendo un nuevo aljibe y adecuando esta parte como residencia y sede de la encomienda. En el siglo XV, el Maestre de la Orden, Alonso Cárdenas, mandó restaurar las murallas y construyó nuevas dependencias. De esta última etapa constructiva es la ermita de Ntra. Sra. de las Nieves, aunque observamos restos de época visigoda en su construcción, así como la posible bodega, cuadras y otros edificios asociados a la casa de la encomienda.
En el siglo XVI, el estado de ruina de la fortaleza, unida a la pérdida de su función defensiva y las incomodidades derivadas de su situación, provoca que los vecinos fueran instalándose en los arrabales, en la parte baja del valle, en el paraje llamado “el Bodegón”, en los alrededores de la ermita de S. Sebastián, conformando la actual población. Dicha ermita, en 1554, pasaría a ser la nueva parroquia, manteniéndose hasta la actualidad. El éxodo de la población se mantiene hasta el siglo XIX, recogiendo Madoz en su diccionario que se otorgó el título de “hijos-dalgos” a quien permaneciese en la fortaleza, aunque sin mucho éxito. En este momento, el pueblo contaba con 117 casas y 430 almas.
La adaptación al valle que forman los cerros del Castillo, la Cezorrera, Escañito y Asomadilla, da como resultado un pueblo que se estira y encarama a las laderas, quedando medio escondido entre un paisaje de campiña y sierra.