Se construyó sobre la antigua iglesia visigoda de Santa Leocadia en el siglo XII. A lo largo de los siglos ha sufrido muchas modificaciones y quedan pocos elementos románicos todavía visibles. 

De esta época nos queda la torre campanario hasta la altura de las campanas, el ábside principal, parte de los muros, una galería de arcos ciegos en el muro sur, las puertas del lado sur y la principal, pese a que esta está escondida detrás una nueva portalada del siglo XVIII.

La portalada sur recuerda mucho a la Puerta del Obispo de la Catedral , está formada por cuatro arquivoltas decoradas con rollos zamoranos. Estas se apoyan en tres pares de columnas, los capiteles de las cuales están decorados con motivos vegetales. Una plancha de hierro pintada de color rojo sustituye la puerta y por lo tanto no se puede acceder al templo por este lugar. El tipo de material y el color no contribuye a ennoblecer este edificio, todo lo contrario. A más a más, durante mi visita durante el verano del 2004 estaba llena de pintadas, dando un aspecto lamentable.

En el siglo XV fue reformada por orden del obispo Meléndez Valdés, los escudos del cual se pueden ver en diferentes partes del edificio. En aquel momento se suprimió la estructura de tres naves por  una única cubierta con bóvedas de crucería. Originariamente el templo tenía planta basilical de tres naves acabadas en tres ábsides semicirculares, un hecho inédito en Zamora. La absidiola norte se perdió y la del lado sur no es visible desde el exterior. Para reforzar la bóveda en el siglo XVIII se construyeron dos arbotantes exteriores que se empotran directamente en el muro del Palacio de los Marqueses de Villagodio , situado justo en frente. También fue necesario un contrafuerte situado sobre el palacio del arciprestado. En el siglo XVIII se culminó la torre campanario.