La nouvelle église dédiée à saint André est construite à l’emplacement du « castell » de Baillestavy. On ignore tout de la date de son édification. Elle peut avoir été édifiée entre le XVIIe et le début du XVIIIe siècle, au moment où l’église vieille est délaissée. Une cloche placée dans le clocher est datée de 1685. L'église remplace un édifice plus ancien dit « de la Torre », attesté dès le XVIIIe siècle. Il est en effet question en 1750 de réparer et d’agrandir l’édifice, jugé trop petit (BLAIZE, GIRMENS, PONSAILLÉ, Revue d’Ille et d’Ailleurs, janvier 1988, p 25). L’inscription « 1762 » sur la porte d’entrée correspond à la date d’achèvement des travaux sans qu'on puisse préciser s'ils concernent la réalisation des chapelles latérales.
Le financement de l’édifice provient de l’argent recueilli en 1761 par la confrérie du Rosaire. Le clocher de l’église fut construit sur les fondations de l’ancien donjon du château, avec réemploi des matériaux des anciennes fortifications. La tribune est construite au début du XVIIIe siècle.