No tenim constància de l'existència d'aquest temple en època antiga, ja que el nom de Villanueva de la Torre és posterior a finals del segle XIV, quan es va construir la gran torre que dóna nom al municipi. De totes maneres un document de l'any 1198 podria fer referència a aquesta població, com una de les possessions del monestir de Santa Maria la Real d'Aguilar de Campoo.

L'església, del segle XII, té una única nau, lleugerament més ampla en el sector oest. La seva capçalera està formada per un absis semicircular, precedit d'un presbiteri de planta trapezoïdal. La nau està dividia en tres trams per mitjà de tres arcs torals, que descansen sobre pilars. Les seves voltes són de creuria, corresponents a una reforma del temple d'època barroca.

L'absis ha estat restaurat recentment. Està dividit en  tres espais mitjançant dues columnes adossades, que estan rematades per capitells esculpits de tipus vegetal.  Una motllura decorada amb puntes de diamant recorre el tambor absidal, per la part exterior, per sota de la finestra .

En l'espai central s'obre una finestra de mig punt i de doble esqueixada, protegida per una arquivolta, que descansa en dues columnes amb capitells esculpits amb grius enfrontats.  L'arc i el guardapols estan decorats amb triangles i puntes de diamant.

Els mateixos motius escultòrics es reprodueixen per la part interior.

En el costat sud del presbiteri trobem una altra finestra. Està decorada amb una arquivolta de puntes de diamant i una imposta esculpida amb dents de serra. Com en el cas de la finestra central, els seus capitells estan decorats amb grius enfrontats. El del costat esquerre és de factura moderna.

Es completa la decoració de la capçalera amb les mènsules, en que es recolza la teulada. Aquestes estan esculpides amb motius geomètrics, però també amb figures humanes, algunes de les quals estan nues en actituds eròtiques.

El presbiteri es cobreix amb una volta de canó lleugerament apuntada. L'intradós del arc on acaba el presbiteri està decorat amb puntes de diamant, el mateix motiu que trobem en l'arc triomfal.

La nau es comunica amb l'absis gràcies a un arc triomfal apuntat, que es recolza en columnes triples. Els capitells de les columnes exteriors estan decorats amb fulles d'acant de factura molt senzilla.

El capitell central del costat de l'evangeli està decorat amb quatre grius enfrontats, entre motius vegetals de tiges entrellaçades.

Per contra, en el costat de l'epístola veiem a Daniel entre els lleons.

Sobre l'arc triomfal s'alça un petit campanar de cadireta d'un sol ull.

A finals del segle XIX es va adossar la sagristia al mur nord. També es va afegir en època moderna el porxo que protegeix la porta d'entrada. Aquesta està formada per una arc de mig punt, protegit per una arquivolta sense decorar.

Als peus de la nau s'alça la torre de campanar, un dels elements més característics del temple. Té planta rectangular. S'accedeix a ella per una porta exterior. Un arc apuntat, avui cegat, comunicava directament la nau amb el campanar. La torre està dividida exteriorment en dos nivells per una motllura. En el pis superior, s'obre una finestra en cadascun dels seus murs. És de tipus geminat amb el capitell llis i protegida per un arc de mig punt.

Es creu que la part baixa de la torre, correspon al sector més antic, probablement formava part d'un edifici anterior.

En l'interior del temple es conserva una talla de la Verge asseguda i amb el Nen a la falda, de finals del segle XIII o principis del XIV.