Los primeros datos documentados sobre Llerena se encuentran en un asentamiento árabe denominado «Ellerina» o «Ellerena», que existía por el siglo XI en torno a la «Fuente Pellejera» que fue muy disputado por musulmanes y cristianos debido a su estratégica situación.

[4]​ Según una leyenda, ante la tremenda resistencia que los moros ofrecían al ataque de los cristianos, cosa que hacía cada vez más difícil la entrada de los cristianos en la ciudad, y cuando la batalla parecía perdida y los santiaguistas empezaban a retirarse, se les apareció la Virgen María mostrándoles en su mano una granada como símbolo de la unidad.

Para conmemorar esta victoria levantaron sobre la mezquita musulmana una iglesia dedicada a la «advocación de la Granada», sobre la que se levantó bajo las ampliaciones impulsadas por los Reyes Católicos, la que conocemos hoy.

[4]​ El recinto amurallado es un ejemplo del modelo de urbanización medieval.

El recinto es ovalado con varias puertas de las que llevan a las calles principales.