La première mention de l’église de Villeneuve apparaît en 1250, selon le Pouillé de Lyon. La paroisse est placée sous le double vocable de saint Clair et sainte Madeleine. On sait peu de choses de l’église ancienne, encore debout en 1830. Il s’agissait d’un édifice modeste, à nef unique et chapelle latérale nord. La visite pastorale de 1654 indique que le chœur était plafonné, « voûté en lambris », la nef, charpentée, n’avait pas de plafond : la même disposition s’observe également à Chanteins. Bien que régulièrement entretenu, en 1827 l'édifice est jugé en très mauvais état et trop exigu au regard de l'accroissement de la population. De plus, la commune doit procéder au transfert du cimetière pour répondre aux exigences hygiénistes de l'époque. Dans un premier temps, la commune envisage d'agrandir l'ancienne église : en 1829, il est procédé à la reconnaissance de deux parcelles utiles à l'agrandissement de l'église et à la reconstruction de son clocher. Finalement, l'église est entièrement démolie, en même temps que celle du hameau d'Agnereins. Les matériaux sont récupérés pour servir à la construction de la nouvelle église.