No tenemos constancia de la existencia de este templo en época antigua, debido a que el nombre de Villanueva de la Torre es posterior a finales del siglo XIV, cuando se construyó la gran torre que da nombre al municipio. De todos modos, un documento del año 1198 podría hacer referencia a esta población, como una de las posesiones del monasterio de Santa Maria la Real de Aguilar de Campoo.

La iglesia, del siglo XII, tiene una única nave, ligeramente más ancha en el sector oeste. Su cabecera está formada por un ábside semicircular, precedido de un presbiterio de planta trapezoidal. La nave está dividía en tres tramos gracias a tres arcos fajones, que descansan sobre pilares. Sus bóvedas son de crucería, correspondientes a una reforma del templo de época barroca.

El ábside ha sido restaurado recientemente. Está dividido en  tres espacios mediante dos columnas adosadas, que están rematadas por capiteles esculpidos de tipo vegetal.  Una imposta decorada con puntas de diamante recorre el tambor absidal, por la parte exterior, por debajo de la ventana .

En el espacio central se abre una ventana de medio punto abocinada, protegida por una arquivolta, que descansa en dos columnas con capiteles esculpidos con grifos enfrentados.  El arco y el guardapolvo están decorados con triángulos y puntas de diamante.

Los mismos motivos escultóricos se reproducen en la parte interior.

En el lado sur del presbiterio encontramos otra ventana. Está decorada con una arquivolta de puntas de diamante y una imposta esculpida con dientes de sierra. Como en el caso de la ventana central, sus capiteles están decorados con grifos enfrentados. El del lado izquierdo es de factura moderna.

Se completa la decoración de la cabecera con los canecillos, en que se apoya el tejado. Están esculpidos con motivos geométricos, pero también con figuras humanas, algunas de las cuales están desnudas en actitudes eróticas.

El presbiterio se cubre con una bóveda de cañón ligeramente apuntada. El intradós del arco dónde acaba el presbiterio está decorado con puntas de diamante, el mismo motivo que encontramos en el arco triunfal.

La nave se comunica con el ábside gracias a un arco triunfal apuntado, que se apoya en columnas triples. Los capiteles de las columnas exteriores están decorados con hojas de acanto de factura muy sencilla.

El capitel central del lado del evangelio está decorado con cuatro grifos enfrentados, entre motivos vegetales de tallos entrelazados.

Por el contrario, en el lado de la epístola vemos a Daniel entre los leones.

Sobre el arco triunfal se levanta una pequeña espadaña.

A finales del siglo XIX se adosó la sacristía en el muro norte. También se añadió en época moderna el pórtico que protege la puerta de entrada. Esta está formada por una arco de medio punto, protegido por una arquivolta sin decorar.

A los pies de la nave se levanta la torre de campanario, uno de los elementos más característicos del templo. Tiene planta rectangular. Se accede a ella por una puerta exterior. Un arco apuntado, hoy cegado, comunicaba directamente la nave con el campanario. La torre está dividida exteriormente en dos niveles por una moldura. En el piso superior, se abre una ventana en cada uno de sus muros. Es de tipo geminado con el capitel liso y protegida por un arco de medio punto.

Se cree que la parte baja de la torre, corresponde al sector más antiguo, probablemente formaba parte de un edificio anterior.

En el interior del templo se conserva una talla de la Virgen sentada y con el Niño en el regazo, de finales del siglo XIII o principios del XIV.