El templo se empezó a edificar en el siglo XI por la cripta, realizada para salvar el desnivel del terreno. En esta primera fase constructiva se realizó el primer tramo de la torre y una parte de la nave. Las obras estuvieron paradas hasta que finalmente se acabó el templo alrededor del año 1169.

Las obras las dirigió el Maestro de Agüero, también conocido por su trabajo en San Juan de la Peña. Esta fue una de sus primeras obras y en las esculturas del tímpano de la portalada sur ya se empiezan a entrever algunos de los que serán sus trazos distintivos.

El templo tiene una única nave dividida en tres tramos y acabada en un ábside semicircular. La bóveda de este ábside tiene la característica de ser de más de un cuarto de esfera. La nave está cubierta con un bóveda de cañón apuntada reforzada por cuatro arcos fajones.

La cripta está formada por un ábside semicircular de diámetro ligeramente superior al de la iglesia. La bóveda está reforzada por gruesos nervios. Exteriormente está construido con sillares de un tono más gris que el resto del templo. Tiene un acceso propio desde el exterior a través de una puerta situada en el inicio del ábside por el lado derecho. Debido a su poca altura, los arcos fajones y las bóvedas arrancan directamente del nivel del suelo.

Destacan las dos portaladas laterales. La del lado norte está tapiada, pero todavía se puede disfrutar del bonito tímpano. Está formada por dos arquivoltas de medio punto que enmarcan este tímpano. Tiene muchas similitudes con una de las portaladas de San Salvador de Ejea de los Caballeros. En él están representados dos ángeles arrodillados que sostienen un crismón.

La del lado sur es todavía más interesante. Está formada por dos arquivoltas de medio punto con un guardapolvo apoyadas en pilastras. En el tímpano se representa el martirio de San Félix, titular del templo. Dos caballos arrastran por los pies al mártir que está rezando. Hay un personaje que azota a los caballos siguiendo las órdenes que le da una persona sentada en una silla y que está aconsejada por un demonio. También podemos ver otro personaje y un ángel que miran de confortar al mártir.