L’église Saint-André développée sur la rive gauche de la rivière de la Lentillà est mentionnée dès 1011 (Cazes, op. cit. p. 35) dans un privilège du pape Serge IV, qui cite l’église de Baillestavy en tant que possession de l’abbaye de Saint-Michel-de-Cuxa, avec la présence d’un habitat groupé autour. Cette bulle indique également que l’église tombe en ruines, ce qui peut justifier son agrandissement et sa transformation aux XIe et XIIe siècles.
L’église fut construite sur un crassier de forge romaine, comme l’atteste la présence de scories (résidus issus de la réduction du minerai) dans le cimetière. Le crassier fonctionna du Ier siècle avant J.-C. au VIe siècle après J.-C., selon les résultats de fouilles effectuées entre 1986 et 1992, dirigées par Gérard Mut (BLAIZE, Yves, GIRMENS, Guy, PONSAILLÉ, Janine et alli. Revue d’Ille et d’Ailleurs, 1988, p. 20.). Un habitat correspondant à une occupation gallo-romaine a également été mis au jour, notamment avec la découverte de fragments d’amphores de type Parcual 1.
A l’origine, la chapelle préromane du Xe siècle présentait une couverture charpentée sur arcs diaphragmes, puis un voutement en berceau dès le IXe siècle. Les travaux effectués entre le XIe et le XIIe siècles ont consisté à remplacer le voutement par une voûte brisée, à renforcer les murs par des arcs formerets et à rajouter l’abside.
L'activité métallurgique perdure à l’époque médiévale à partir du XIIIe siècle, comme l’atteste les fondations d’un bassin, d’un puits à trémie et de fours de réduction du minerai (bas-fourneaux) découverts lors des fouilles. Si l’un des fours encore sous terre n’a pas encore été fouillé, les vestiges du second ont été découverts lors de la réfection du mur Nord du cimetière en 1998.
Principal lieu de culte de Baillestavy, elle est abandonnée en 1665 pour l’église dite « de la Torre ». La chapelle latérale au Nord ainsi qu’une petite chapelle au Sud furent construites entre le XVIe et le XVIIIe siècles, comme en attestent les résultats de fouille effectuée en 2012. Des travaux de restauration ont été effectués en 1977, notamment au niveau du clocher-tour.
Les fouilles réalisées en 2012 par le Pôle Archéologique Départemental (66) ont révélé la présence de fragments d’enduits peints (provenant de l’abside ?), d’un ferrier antique à l’entrée du chœur ainsi que d’une sépulture non datée du côté de la chapelle Nord. Le ferrier a également été retrouvé contre le mur Ouest, à 0,75 m de profondeur.