Por la ubicación de este templo, que se encuentra en el lado más meridional y elevado del primer recinto del castillo, hace pensar que fue levantado en el solar la antigua Mezquita musulmana, necesaria en una plaza almohade de tal importancia y con el supuesto elevado número de población que albergaba su recinto.
No estaría de más destacar que las últimas investigaciones sobre este templo, según varios parámetros analizados tras las obras de reconstrucción, limpieza, y excavación del cementerio medieval que lo rodeaba en su parte meridional, apuntan con seguridad a que el templo conseva paramentos de la mezquita musulmana, reformada y ampliada posteriormente tras la reconquista. Así lo afirma Gutiérrez Ayuso tras analizar la caja de muros primitiva y la misma cimentación del templo en varias partes desescombradas, así como su técnica constructiva y materiales.
Bajo la advocación de Nuestra Señora, posteriormente de Santa Ana, Frey Ruy Vázquez que fue Maestre hasta 1318 y que de su antecesor don Suero Pérez Maldonado había recibido la Encomienda de Magacela, fundó esta parroquia y organizó la vida religiosa en la villa construyendo este templo.
El monumento es de planta única rectangular con tres cajas de muros adosadas formando capillas, dos de éstas al muro de la Epístola y otro cubo a los pies que son claro testimonio de añadidos a lo largo del tiempo debidos a causas diversas. El edificio casi en su totalidad se construyó con mampostería y ladrillo, relegando la piedra de granito labrada a contrafuertes exteriores, el arco toral y los nervios de la bóveda del altar mayor.
La cubierta era de madera, hoy repuesta de nuevo, señalándose en el segundo cuarto del siglo XVIII que había sido sustituida por una nueva, y de la que en 1950 se informa que se había desplomado parte de ella; sobre ésta, arcos diafragma sustentaban el tejado a dos vertientes que aún se puede apreciar en fotografías de esa última fecha referida.
La cabecera, cubierta con bóveda de ladrillo y nervadura de crucería, pone de manifiesto una más que significativa modificación de la fábrica original, una ampliación del templo llevada a cabo entre 1563 y 1584 como ya informa Alonso Gutiérrez. "La solicitud de obras llega al Consejo de Órdenes, y tras las pertinentes diligencias, fue aprobado en 8 de octubre de 1562 que, de las rentas de yervas del partido de La Serena, se entregaran 600 ducados (225.000 maravedís) al prior de Magacela para «acreçentar y ensanchar la yglesia de la villa de Magazela», término que tuvo efecto con la recepción del dinero en 30 de abril de 1563". El encargado de la obra es Duarte Muñoz, que en la última semana de agosto de 1567 asienta la obra y se concluyen los trabajos en teoría. Pero la construcción de la capilla mayor debió quedarse en la caja de muros, pues nada se menciona de la cubierta y abovedamiento. En este estado permaneció el edificio una década, coincidiendo con los peores años económicos de la Monarquía. En 1578 se ordena que se ha de «...continuar y acabar la dicha obra y cubrir la dicha capilla conforme a la dicha tassacion que della esta fecha...». La visita de Rodríguez de Ledesma a la iglesia se produjo hacia 1584, y la continuación de la obra se remata después de ésta, tal vez tarde por haberse demorado el pago de los 853 ducados y medio del coste de la intervención. En 1585, fecha en la que ya se solicita el retablo para el altar mayor, está terminada la obra. El retablo fue finalmente realizado por Juan Sánchez Contreras, vecino de Mérida, en el año 1592 tras habérsele adjudicado el proyecto por un total de 330 ducados según consta en el libramiento de Felipe II fechado en San Lorenzo el Real el 25 de marzo de 1589.
Coronando el retablo, insertados en la pared había dos escudos de granito. El más vistoso y central representa las armas de Felipe II antes de la anexión con Portugal, anterior a 1581. El otro es del Prior de Magacela Frey don Francisco Rol de Acosta, del que aparece documentación al frente del Priorato desde 1552 hasta 1584. Naranjo Alonso señala que fue éste «el Prior que tuvo Magacela en la fecha de su paso por este territorio del Rey don Felipe II para la guerra de Anexión del trono de Portugal».

El arco toral inmediato al altar es, como ya hemos señalado, a diferencia de los demás de «ladrillo y cal», de cantería de granito, y sabemos que estaba decorado con cinco cruces. La bóveda del altar persiste gracias a la solidez de los aparejos graníticos que componen los nervios que descansan sobre robustas ménsulas en cada esquina y que a su vez distribuyen el peso a unos sólidos contrafuertes exteriores.
En el lado de la Epístola de este altar mayor se encuentra la sacristía del templo, siendo a su vez uno de los tres cubos adosados ya mencionados. Es de bóveda de aristas, solada de baldosas, con hornacinas en los muros laterales y una ventana al mediodía. En este mismo lado de la Epístola, en el tramo de nave inmediato al arco toral, hay otra capilla cubierta con bóveda de dos tramos, una de cañón separada de otra de aristas por un arco fajón. En el segundo cuarto del siglo XVIII recibía el nombre de “Capilla del Santísimo Cristo de Afligidos” por contener la talla de un Cristo crucificado. Al fondo de ésta se conserva el poyo de piedra a modo de Altar y que debió ser soporte de la imagen o retablo. En los muros laterales aún se pueden apreciar entre las numerosas capas de cal los restos de pintura que la decoraban. Además, sabemos que dicha capilla fue construida con la limosna de los vecinos de la villa, citándose como nueva en 1742.
El último de los cuerpos añadidos a la planta del templo está situado a los pies de éste, y justo debajo de la desaparecida tribuna. Se trata de una capilla con bóveda de medio cañón y solado de baldosas destinada a cumplir la función de baptisterio.
La tribuna, de madera de pino, se sustentaba mediante una columna «de piedra de canteria» y se subía a ella por una escalera de piedra.
Las puertas de entrada, abiertas en ambos muros del Evangelio y de la Epístola, son dos interesantes portadas mudéjares de ladrillo, según Pilar Mogollón, construidas en el siglo XV. Éstas estaban coronadas por esculturas de leones, dos en la del muro del Evangelio y una en la de la Epístola. En la portada del muro septentrional o del Evangelio aún se ven los huecos que dejaron al extraerse. La puerta meridional todavía conserva el único león que corona el estribo semicilíndrico de ladrillo del lado izquierdo de la portada.
La portada norte está compuesta por un arco de medio punto sobre el que corre en su parte superior una banda de ladrillos en esquinilla. Inmediatamente encima de ésta, se desarrollan una serie de canes escalonados sobre los que va una moldura estrecha en saledizo. Dos pequeños estribos, a modo de pilastras, la limitan lateralmente
La segunda puerta, que se abre en el muro de la Epístola, es muy similar. Está formada por un arco de medio punto que apoya sobre pilastras rematadas en impostas. En su parte superior corre horizontalmente una franja decorativa de ladrillos en dientes de sierra. Está limitada en su lado derecho por el muro de la capilla inmediata que sobresale en su exterior y en el lado izquierdo por un pequeño estribo semicilíndrico coronado por la figura de león realizada en granito.
La descripción del templo en 1742 nos pone de manifiesto, que al ser pequeño el edificio, había algunas dependencias anejas a la iglesia para suplir problemas de espacio. Sabemos que la ornamentación del templo se componía notable decoración esgrafiada del siglo XVIII a base de volutas y motivos vegetales neoclásicos. Las rejas de sus vanos, con remate forjado en alcachofas, eran características y muy representativas de la rejería del siglo XVII. De las tres que se documentaban en 1950, se conservaban todas hasta hace poco, ya que hace algunos años alguien arrancó la de la ventana de la sacristía.
Esteban R. Amaya, Jiménez Navarro y Fernández Oxea explican las fases constructivas del templo de la manera que sigue, confirmada tras las últimas intervenciones en el templo. Según éstos, en un principio se siguen utilizando las cajas de muros de la antigua mezquita habilitadas al culto cristiano hasta que a comienzos del siglo XVI los caballeros de la Orden de Alcántara acometieron su ampliación, «respetando la disposición anterior y recubriendo con obra moderna la primitiva estructura, utilizando ... mano de obra mudéjar».
Hasta hace poco, y gracias a unas obras de reconstrucción, la iglesia se encontraba en un estado de ruina lamentable; situación que se venía agravando desde de hace unos cincuenta años, cuando ya se denunciaba su mal estado a pesar de que estaba prácticamente completa.
De los dos retablos Mayores que constan documentalmente, el primero que presidió el Altar Mayor, según hemos podido saber gracias a la descripción del visitador don Diego de Sandoval y Pacheco y analizada por Gutiérrez Ayuso, era de tres cuerpos e igual número de calles. Conocemos más detalles gracias las trazas del retablo renacentista sacadas a la luz por el mismo Gutiérrez Ayuso y Martín Nieto en un estudio, sabiendo el coste total de la obra, proceso de ejecución y autoría. Se talló según modelo presentado por el maestro pintor residente en Campanario Juan Bautista, discípulo desconocido de Luis de Morales y el campanariense Alonso de Valdivia, ensamblador, en 1588. El retablo fue finalmente realizado por Juan Sánchez Contreras, pintor y escultor vecino de Mérida, en el año 1592. Se le adjudica el proyecto tras pujar con los dos artistas que presentan las trazas y ganarles como mejor postor por un total de 330 ducados (123.750 maravedís) según consta en el libramiento de Felipe II fechado en San Lorenzo el Real el 25 de marzo de 1589. Todo esto pese a que el Prior de Magacela, Frey Don Juan de Grijota, quería a Juan Bautista como pintor por no fiarse de las cualidades artísticas de Sánchez Contreras: «...dixo que por quanto el dicho Juan Sanchez de Contreras no hes conoçido en este partido, que en quanto a la madera e talla se le admite la postura, y en cuanto a la pintura no, por no ser conoçido en su arte, porque a personas ay que se les a de dar dinero porque pinten y a ottros porque no pinten, porque estan muchos retablos en este partido perdidos por darse a personas que no tienen la sufiçiençia en su arte que conviene, y hesto rrespondió y que Juan Bautista que tiene la dicha hobra, hiço los rretablos del convento de Alcantara y ottros muchos para el Obispo de Coria, y en aquel Obispado, e todos con mucha satisfaçion y an pasado por de mano de Morales con pintarlos el dicho Juan Bautista, aviendolos pintado y debuxado el dicho Juan Bautista, y porque su Magestad dé los quattroçientos ducados para haçer el dicho retablo, pintura y talla, conviene a su rreal serviçio que se dé a personas que sean buenos ofiçiales, e que no pidan cada dia rreparos para el dicho rretablo y lo firmó ... ». (A. Gutiérrez Ayuso y D. Á. Martín Nieto: La iglesia del castillo de Magacela. Un proyecto de retablo de Juan Bautista, discípulo desconocido de Luis de Morales. Badajoz, 2004).
Avanzando en el tiempo, el nuevo retablo que se describe en 1742 se aparta estilísticamente del anterior, al que sustituyó con toda seguridad sin haber habido otra obra intermedia como apunta A. Gutiérrez.
Entre los objetos litúrgicos y ornamentos de la Parroquia, en los años 30 del siglo XVII se documentan numerosas piezas que se relacionan en la obra antes citada, así como un detallado proceso de necesidades ornamentales y obras de acondicionamiento y ampliación del templo.
Mención especial merece la pila bautismal, que se conserva en el baptisterio de la nueva parroquial de Santa Ana, obra labrada de finales del XV según este autor citado