Iglesia mudéjar que seguía la estructura típica de nave única, dividida en cuatro tramos, con capillas abiertas entre los contrafuertes y cabecera poligonal de cinco lados. El sistema de cubrición utiliza bóvedas de crucería simple para la nave y cañón apuntado en sentido transversal al eje de la iglesia para las capillas. Los paramentos al interior se hallaban recorridos por una serie de capiteles sencillos sobre los que cargan los nervios de la cubierta, coronando un fuste que fue cortado a mitad de su altura en el siglo XVI en la reforma llevada a cabo por Juan de Miraso. Los gruesos muros de la cabecera hacen innecesario el uso de contrafuertes exteriores.
Una serie de vanos apuntados recorren los muros, abiertos uno por cada tramo de la nave y en cada paño del ábside.
En una segunda etapa constructiva que se extiende hasta los primeros años del siglo XV con una serie de reformas y ampliaciones en la iglesia que transformaron de manera radical su aspecto mudéjar. Se añaden dos naves laterales de anchura desigual que rodean la totalidad de la planta mudéjar de la iglesia, originando en la zona de la cabecera un deambulatorio o girola que circunda el ábside prolongándose hacia la parte occidental o tramo de los pies donde forman una especie de atrio o claustra, quedando encerrada la torre dentro de la edificación. Las primitivas capillas desaparecen como tales para convertirse en pasos hacia las naves laterales como arcos formeros muy profundos. Estas naves laterales se cubrieron con crucería simple.
En 1571, Juan de Miraso reforma parte de la decoración interior, que aún se puede observar en algunos de los vanos que aparecen decorados con motivos renacentistas, y corta los fustes de las columnas que apeaban los nervios de las bóvedas.
La iglesia debió tener originalmente una decoración agramilada y pintada, tal y como se ha puesto de manifiesto en la restauración llevada a cabo por el arquitecto Ramiro Moya, en la que se descubrió esta decoración en una de las capillas laterales del lado izquierdo, restituyéndola en el resto de las capillas.
Durante los siglos XVI, XVII y XVIII se añadirían varias capillas en el lado derecho, cabecera y pies de la iglesia, siendo cubiertas las de mayor antigüedad con bóvedas de terceletes y crucería estrellada, y las más modernas con cúpulas sobre pechinas, con o sin linterna.
La fachada sur constituye la fachada principal, cuyo aspecto se modificó con la restauración efectuada que sacó el ladrillo en un intento de devolver a los muros su aspecto primitivo. Esta fachada recae a la calle de San Pablo, y es el resultado de tres etapas constructivas, correspondiendo la portada a la más antigua; ésta es de estilo herreriano, construida en el siglo XVII, y se abre en arco de medio punto con rosca resaltada con recuadros, coronada por una hornacina que alberga una popular talla de Nuestra Señora del Pópulo.
Durante el siglo XVIII se efectúan una serie de reformas en la fachada a cargo de Joaquín Insausti, entre 1795 y 1798, obras financiadas en su mayor parte por Miguel de Losilla y Rosa Tenías, consistentes en el cerramiento de la portada ligeramente abocinada mediante un arco de medio punto enmarcado por pilastras toscanas, con fuste estriado, que sostienen entablamento y frontón. El muro fue revestido de piedra, y se colocaron pilastras lisas, sosteniendo una cornisa superior y se abrieron sus muros mediante hornacinas con jarrones.
En 1857 Pedro Martínez Sangrós reforma el anterior proyecto neoclásico de la fachada añadiendo una escultura de San Pablo, obra de Antonio Palao, coronando el frontón.
Finalmente la última restauración eliminará todo a excepción de la puerta principal de ingreso.
Iglesia mudéjar que ejercería una notable influencia en la construcción de otras en la Zaragoza de aquellos años.
La portada norte se relaciona en su conjunto con la portada de la Seo de Huesca.