L’église Saint-Félix est mentionnée pour la première fois en 865 (Sanctus Felix) [CAZES, 1977, p.12], dans un document relatif à un litige sur la propriété du « Vilar de Mata », situé dans les limites de la villa de Prada. Considéré comme étant le plus ancien document écrit conservé aux Archives Départementales des Pyrénées-Orientales, le plaid évoqué est présidé par le comte Salon, issu de la lignée des comtes de Cerdagne. Selon le texte historique, la villa de Prada ainsi que le vilar de Mata confrontent Saint-Félix.
De nombreuses modifications ont été apportées à l’édifice, entre les 14e et 19e siècles. Au 14e siècle, deux chapelles latérales sont ajoutées au Nord et au Sud, ainsi que deux sacristies [CCRP, 2005]. Probablement modifié une première fois au cours du 14e siècle, le chevet d’origine situé à l’Est est détruit aux 17e et 18e siècles, afin de construire une nouvelle entrée matérialisée par un porche. De plus, des agrandissements sont apportés, avec la construction des chapelles de Sainte Apolline et de Notre Dame du Rosaire, baptisées en 1741 par l’abbé de Saint-Michel de Cuxa. Au 18e siècle, l’église placée sous le vocable de Saint-Félix et Saint-Germain, bénéficie de réparations au niveau de son clocher-tour (1770). Ce dernier fait à nouveau l’objet de travaux au 19e siècle, dont le projet en date du 12 mai 1826 indique qu’il « menace ruine » [CCRP, 2005]. Les travaux estimés à 1060 francs, débutent le 1er octobre 1836. Le clocher-tour était à l’origine couronné de créneaux pouvant être datés des 13e – 14e siècles, certainement supprimés au 19e siècle.
L’inventaire réalisé entre 1906 et 1907 à la suite de la séparation de l’église et de l’Etat, distingue deux parties distinctes de l’église. Il explique que « la partie ancienne a été bâtie par la générosité et les sacrifices des anciens habitants de Codalet ». L’abbé Font (1831-1907) « second titulaire de la paroisse depuis son érection en succursale qui a eu lieu en 1846, (…) déploie toute son ardeur, tout son zèle pour la restaurer, l’embellir, la décorer » [A.D. 66 : 8 V 31]. Le curé a notamment entrepris la restauration des quatre chapelles de l’église, financée grâce aux dons des habitants les plus aisés de Codalet. Enfin, la partie « nouvelle » de l’édifice relative à « l’agrandissement de 6,50 m de long » (projet dressé en 1891), A été construite « sur un une partie d’un terrain appartenant à Monsieur Félip instituteur en retraite, et acheté par la Fabrique ». Le plan des lieux dressé le 2 août 1891, projette la partie à acquérir, destinée à agrandir le côté Sud du vestibule de l’église [A.D. 66 : 2 OP 970]. Par ailleurs, un pressoir est indiqué à l’emplacement de la chapelle qui jouxte le vestibule au Nord.
