El templo fue fundado en el siglo XIV, entre 1385 y 1387 por Garcí Fernández de Villagarcía, con un estilo gótico-mudéjar. La construcción se levantó sobre una antigua ermita, edificada en el siglo XIII tras la reconquista de Llerena.[1]
En el siglo XVI, la Inquisición modifica el templo y añade en la fachada frontal soportales y arcos. También modifica la torre, donde sustituye la parte superior por una nueva de estilo renacentista, que se apoya sobre la parte baja de la antigua de estilo mudéjar.[2] Esta parte mudéjar de la torre, junto a la capilla de San Juan o de la familia Zapata, de estilo gótico con detalles renacentistas, y la capilla del Prior, fundada en 1580 por Gonzalo de la Fuente y de estilo renacentista, constituyen las únicas partes que se conservan hoy en día de la edificación original.[1][3]
En 1744, con la iglesia en estado ruinoso, se encarga a José de Hermosilla la creación de un proyecto para su reconstrucción.[2] A él se le atribuyen las partes de estilo barroco del templo, como la parte inferior de la fachada frontal. También en el siglo XVIII, se añade la parte superior de dicha fachada, de estilo mudéjar, que cumplía una función de palco para presenciar los actos que se realizaban en la actual plaza de España.[3]
El retablo mayor y la imagen de la Virgen de la Granada, originalmente románica, junto a otras obras de arte, fueron destruidos en la Guerra Civil. El retablo y la imagen de la Virgen fueron reemplazados por unos nuevos a consecuencia de ello.[2][4]
El 24 de enero de 1967, se publicaba en el Boletín Oficial del Estado un Decreto que declaraba a Llerena como conjunto histórico artístico, donde se incluye a la iglesia de Nuestra Señora de la Granada.[5] Años más tarde, el 15 de abril de 1983, el Boletín Oficial del Estado publicaba una resolución de 25 de febrero de 1983, donde se iniciaba el proceso de tramitación para declarar la iglesia como monumento histórico-artístico.[6]