Évolution de l'église de Villeneuve de Mézin au cours des siècles, d'après Stéphane Thouin.
Coupe de l'église au XIIIesiècle d'après Stéphane Thouin
L'église faisait partie du castrum de Villeneuve situé à la limite de la forêt landaise. Le castrum de Villeneuve est mentionné en 1259 dans un hommage au comte de Toulouse. Bernard de Grauhet rend hommage en 1287 pour ce castrum. Il subsiste de l'enceinte de ce dernier un mur à l'ouest ainsi qu'une porte fortifiée. L'église faisait partie du système défensif.
Il ne reste rien de l'église du Xesiècle. L'église actuelle date de la fin du XIIesiècle ou du début du XIIIesiècle. Elle comprend alors une nef de deux travées placée contre une tour de l'enceinte qui devait servir de donjon. Un élément du mur d'enceinte vient en appui contre la tour. La nef primitive n'était pas voûtée et formait une salle rectangulaire. Un plancher divisait le bâtiment en deux dans le sens de la hauteur, le premier étage servant de logement à la garnison accessible par un escalier situé dans l’épaisseur du mur de façade. Il permettait l’accès au chemin de ronde et aux fortifications plus ou moins mobiles: des hourds de bois, en encorbellement au-dessus du vide, interdisaient l’approche d’assaillants éventuels au pied du mur. Dans la nef proprement dite, les ouvertures sont étroites, comme des meurtrières. Les hourds ont été en service jusqu'au XVesiècle bien qu'ils aient souvent été remplacé depuis le XIIesiècle par des mâchicoulis.
Le chœur de l'église voûté en berceau brisé se trouve au rez-de-chaussée de l'ancienne tour. Il est surmonté par les étages de la tour. Le mur ouest de la tour a été surélevé par un clocher-mur. Les voûtes actuelles de la nef ont remplacé, au XVIesiècle, le plancher initial de la salle des gardes. La nef est alors divisée en deux travées. Les voûtes s’appuient sur des colonnes engagées dans les murs et sur des nervures.
Au XVIesiècle, le mur de droite fut percé de deux arcades pour donner accès à une grande chapelle latérale également voûtée en croisées d’ogives dont le chevet est le mur d'enceinte. Au XVIIesiècle, cette chapelle fut décorée de peintures de facture harmonieuse.
La porte d’entrée en plein cintre est à trois ressauts et la décoration de têtes de clous. Une pierre gravée, encastrée au-dessus de la porte, laisse apparaître le monogramme du Christ (Croix, Alpha Omega ainsi que X et P) mais aussi les lettres irrégulièrement disposées: B A I G S N T, dont la signification n’a pas été clairement élucidée par les spécialistes.