En los años 1928-30 existió en Villanueva el primer equipo formal denominado "Vandalia", que vestía camisola azul celeste y pantalón blanco, tenía el Campo de Fútbol en la Carreterilla de la Fuensanta.

El primer equipo denominado CD Villanueva data de los años 1931/32 y vestía camiseta y pantalón blanco, misma vestimenta que en la actualidad.
Tras el parón de la Guerra Civil llegaría una de las épocas más esplendorosas del club, con grandes jugadores como los hermanos Quesada, Ramoní, Juanito Marco "Sardina" y Rafael, entre otros. La afición despertó y el Ayuntamiento construyó un nuevo campo de grandes dimensiones. Vinieron jugadores de Madrid, Vozmediano y otras localidades para completar un equipo Campeón Provincial con gran margen de puntos sobre el segundo clasificado.

Al marcharse los jugadores forasteros, una gran camada de jóvenes villanovenses se abrió paso en el equipo. Domínguez, Fuentes, Naranjo, Yeste, los hermanos Uceda, Montáñez y Antoñito Fraile, entre otros. En esta época se empezó a pagar a los jugadores. El que más cobraba recibía diez duros.

Después llegaría una gran temporada de decadencia del fútbol local por falta de instalaciones, que sería recuperada en los años 70 y 80. El equipo militó durante la década de los 80 un total de seis temporadas consecutivas en el grupo IX de 3ª División asumiendo grandes logros, como la tercera plaza conseguida en la temporada 82-83 que garantizaba la participación en Copa del Rey para el año siguiente donde se enfrentó al Granada CF. Posteriormente, disputó la competición copera en dos ediciones más, cayendo eliminado en ambas ante el Iliturgi CF y ante el CD Málaga, que militaba en la temporada 1985-86 en Segunda. Además, disputó la Copa de la Liga ante el Sevilla Atlético. El equipo acabó descendiendo a Regional Preferente en la temporada 1987/88. En la siguiente, un joven Gregorio Manzano llegó al banquillo del San Blas y estuvo muy cerca de lograr el regreso a Tercera. En la última eliminatoria, cayeron en la tanda de penaltis ante el Vélez CF. El equipo continuó compitiendo hasta la campaña 1992 - 1993.

El CD Villanueva volvió al fútbol federado en la temporada 1999-00, logrando el ascenso a Regional Preferente. En la siguiente campaña protagonizó un año notable pero el equipo acabó desapareciendo. Tras varios años sin fútbol sénior en el pueblo, en la temporada 2005-06 se recuperó. Y desde entonces el equipo ha estado compitiendo ininterrumpidamente. Ese primer año se logró el ascenso a Regional Preferente. En la siguiente, el CD Villanueva descendió, pero en la 2007-08 volvió a la máxima categoría provincial, en la que permaneció hasta el descenso de la 2010-2011. Tras un largo periplo por la Primera Provincial y Tercera Andaluza, el club consiguió ascender a Primera Andaluza en la campaña 2015-2016, de la mano de Alejandro Arce en el banquillo y de Esteban Siles como máximo mandatario de la entidad. En la temporada siguiente, consiguió in extremis la salvación. En la 2017/2018, el equipo fue quinto. Y en la 2018/2019 logró el gran hito de la última década, proclamándose campeón de la Primera Andaluza, con Fernando Carriquí como entrenador e Ignacio Moreno como presidente, y logrando el ascenso a División de Honor, una categoría autonómica casi 3 décadas más tarde. El equipo ha disputado esta categoría en dos temporadas siendo su presidente Hugo Navarrete. En la primera, la pandemia de la COVID-19 obligó a la suspensión de la misma cuando el plantel villanovense marchaba colista. En la segunda, la 2020-2021, con Joaquín Pérez Pareja como técnico, lucharon por la permanencia hasta las últimas jornadas pero no lograron el objetivo deportivo.

La temporada 2021-22 fue la primera de Dolores Romero como presidenta y de Manuel Á. Redondo Soto como técnico de una escuadra que finalizó en quinta posición en la fase de ascenso a DH. En la temporada 2022-23, se mantiene la junta directiva y el máximo responsable técnico con un proyecto de casa.