Son varios los nombres y títulos que a lo largo de su historia ha ostentado la actual Villanueva de la Serena. Aldeanueva  (Aldea Nueva, o Aldea Nueva de Medellín) es el primer nombre que conocemos. La aldea dependía desde 1270 de la jurisdicción de Medellín. Fernando IV la donó en 1303 a la Orden de Alcántara para su repoblación, bajo el nombre de Aldeanueva de los Freires. En 1309 nos encontramos con el nombre deVillanueva de Lares aludiendo a la adscripción de la Villa a la Encomienda de Lares.Más adelante el nombre se cambió por el de Villanueva de Magacela al pasar a depender de esta villa.

Finalmente, su actual denominación Villanueva de la Serena la encontramos por primera vez el 10 de Mayo de 1423, en un privilegio firmado por el Maestre Frey Don Juan de Sotomayor, en el que se libera definitivamente de la Villa de Magacela.

Villanueva de la Serena nació a mediados del siglo XIII, fundada por unos labradores de Medellín, que la bautizaron con el nombre de Aldeanueva. Desde el año 1160 tenemos noticias de su repoblación.

En la España Romana hubo cerca de Villanueva de la Serena un poblado llamado Portículus, de situación elevada y formado por un pequeño puerto, que venía a ser entrada y camino de la Serena. Portículus significaba puerta y puerto, llave, entrada y paso. Y en realidad lo era, desde Lusitania a la Beturia. Se han encontrado algunos restos Arqueológicos, entre ellos una lápida con la inscripción: ”P.TALIUS:Q.F.PAP.LEG.X/HIC SITUS.EST.»

Como precedente directo del núcleo que conocemos hoy, aparece Vesci, establecida en el siglo I d.c. El Marqués Torres Cabrera en su libro; Páginas de Extremadura: Villanueva de la Serena (1900), lo afirma y aporta el hallazgo de diversos testimonios arqueológicos y epigráficos. Noticia que también recoge Muñon Gallardo enApuntes para la historia de Villanueva de la Serena. Otros autores, como Ortiz de Thovar, que atribuyen a la localidad un origen más antiguo, pues se remontan a la época de los túrdulos, noticia que recoge Bernabé Moreno de Vargas en Historia de Merida.

En el siglo X los árabes levantaron un castillo en el margen derecho del rio Guadiana que se llamó Almojáfar o Mojáfar que se trataba de una atalaya o puesto de defensa del rio en esta zona.

En 1303 el núcleo fue cedido por Fernando IV a la Orden de Alcántara para su repoblación, bajo el nombre de Aldeanueva. En 1423 alcanzó el rango de Villa, contando con una cerca amurallada de la que no se conserva ningún vestigio, pero cuyo trazado resulta bien conocido.

En 1504 se instalaba en ella el Priorato de la Orden trasladado desde Magacela. Desde esa época la población luce en su escudo el lema que la señala como Puerta de la Serena.

A finales del siglo XVI y comienzos del XVII (con una población aproximada de 3.500 habitantes), se convirtió en el municipio más importante de la comunidad de Villa y Tierra de Magacela y en la cabeza de los 18 pueblos enclavados en el territorio de la Real Dehesa de la Serena .La población se sitúa en el borde occidental de la comarca, en el ámbito donde se solapan las comarcas de Vegas Altas del Guadiana y las llanuras de La Serena. Junto con Siruela, fue la sede de las reuniones de la Mesta, distinguiéndose a partir del siglo XVII como uno de los centros más florecientes de la región.

En el XIX (1856) recibió de Isabel II el título de Ciudad, al mismo tiempo que Don Benito. A la caída del Antiguo Régimen la localidad se constituye como municipio constitucional en la región de Extremadura. Desde 1834 es cabecera y sede del Partido judicial de Villanueva de la Serena. En el censo de 1842 contaba con 1997 hogares y 7296 vecinos.

Durante la Guerra Civil, Villanueva fue leal a la República, cayendo en poder del bando sublevado en julio de 1938 y sufriendo entonces los republicanos una violenta represión por parte de las fuerzas franquistas, cuyas consecuencias aún perduran dado que no se han hallado los cuerpos de los republicanos fusilados y enterrados en algún paraje desconocido próximo a la localidad de Medellín

Villanueva de la Serena ha experimentado en los últimos tiempos un extraordinario desarrollo, habiéndose convertido en pocas décadas en una ciudad moderna, abierta y dinámica, muy pujante en el terreno económico, social y cultural, constituyendo, junto con Don Benito, un poderoso centro de servicios, cuya influencia se proyecta con fuerza sobre todo el territorio circundante.