Si para muchas poblaciones extremeñas la relación con las Órdenes Militares revisten importancia muy destacada, para Llerena la conexión con la Orden de Santiago constituye la entraña misma de su ser. Porque Llerena fue el corazón mismo de esta Institución en Extremadura, al igual que la Orden fue el alma de la ciudad.

De tal modo, la identificación entre ambas entidades, Llerena y Orden de Santiago, alcanzó tal grado, que bien puede afirmarse que ninguna de las dos resulta concebible separada de la otra. Así lo proclama con ajustada veracidad la vieja copla popular:

Llerena con ser Ciudad
vale más que Badajoz;
Llerena tiene la Orden
de San Marcos de León

Los primeros antecedentes documentados sobre la población se encuentran en un asentamiento árabe denominado Ellerina o Ellerena, nucleado ya en el siglo XI en torno a la Fuente Pellejera. El enclave, muy disputado por musulmanes y cristianos debido a su estratégica situación, resultó ocupado definitivamente por Pelay Pérez Correa en 1.243.

Con ocasión de esta conquista es cuando tuvo lugar el milagro con el que se conecta la más emblemática de las realizaciones de la ciudad: la iglesia de Ntra. Sra. de la Granada.

Ante la resistencia de los moros frente al ataque de los cristianos, la entrada de éstos en la plaza se hacía cada vez más difícil. Cuando la empresa parecía imposible y los santiaguistas comenzaban a retirarse, cuenta la hermosa leyenda que se les apareció la Virgen María mostrando en la mano una granada como símbolo de la unidad. La visión enardeció su espíritu, haciéndoles culminar la victoria.

Para conmemorarla erigieron sobre la mezquita musulmana una iglesia dedicada a la advocación de la Granada, sobre la que más tarde se levantaría la que, bajo las ampliaciones impulsadas por los Reyes Católicos y otras, es la que hoy conocemos.