El temple es va començar a edificar al segle XI per la cripta, realitzada per salvar el desnivell del terreny. En aquesta primera fase constructiva es va realitzar el primer tram de la torre i una part de la nau. Les obres van estar aturades fins que finalment es va acabar el temple pels volts de l'any 1169.

Les obres les va dirigir el Mestre de Agüero, també conegut pel seu treball a Sant Joan de la Penya. Aquesta va ser una de les seves primeres obres i en les escultures del timpà de la portalada sud ja es comencen a entreveure alguns dels que seran els seus trets distintius.

El temple té una única nau dividida en tres trams i acabada en un absis semicircular.

La volta d'aquest absis té la característica de ser de més d'un quart d'esfera. La nau està coberta amb un volta de canó apuntada, que està reforçada per tres arcs doblers. Els arcs es recolzen en columnes adossades a pilastres, que exteriorment es transformen en contraforts.

Els capitells dels arcs doblers estan esculpits amb motius vegetals de factura molt senzilla, mentre que els de l'arc triomfal són llisos. 

La cripta està formada per un absis semicircular de diàmetre lleugerament superior al de l'església.

La volta està reforçada per gruixuts nervis. Exteriorment està fet amb carreus d'un to més grisos que la resta del temple.

Té un accés propi des de l'exterior a través d'una porta situada en l'inici de l'absis pel costat dret. Degut a la seva poca alçada els arcs torals i les voltes arrenquen directament del nivell del terra.

Malauradament, no us podem oferir cap imatge de l'interior de la cripta, doncs no està inclosa en les visites turístiques, malgrat ser la única església del terme municipal d'Uncastillo que té cripta.

Destaquen les dos portalades laterals. La del costat nord està tapiada, però encara es pot gaudir del bonic timpà. Està formada per dues arquivoltes de mig punt que emmarquen aquest timpà.

Té moltes similituds amb la portalada oest de Sant Salvador d'Ejea de los Caballeros. En ell estan representats dos àngels agenollats que sostenen un crismó.

La del costat sud es encara més interessant. Està formada per dues arquivoltes de mig punt amb un guardapols recolzades en pilastres.

En el timpà es representa el martiri de Sant Fèlix, titular del temple. Dos cavalls arrosseguen pels peus al màrtir que està pregant. Hi ha un personatge que assota als cavalls seguint les ordres que li dóna una persona asseguda en una cadira i que està aconsellada per un dimoni. També podem veure un altre personatge i un àngel que miren de confortar al màrtir.

Sostenen el timpà dos muntants decorats amb bèsties que estan devorant a figures humanes. Les seves traces ja comencen a desvetllar el que serà l'estil característic del Mestre d'Agüero, tot i que encara poc refinat en tractar-se d'una obra primerenca.

A l'esquerra de la porta veiem una inscripció molt erosionada i distribuïda en dos carreus. També trobem un làpida funerària escrita en un altre carreu.

En l'interior del temple es conserva una pila baptismal de planta quadrada i que s'ha reaprofitat com a base d'altar.