Las tierras que hoy ocupa Villanueva de la Reina fueron muy transitadas en la Antigüedad, por estar situadas en la vía de Cástulo a Iliturgi y, por tanto, por formar parte de la Vía Augusta. En los Vasos de Vicarello, en los que aparece la ruta de Cádiz a Roma por Cástulo, se menciona una parada en Ad Noulas o Nobia, que por su disposición poco después de Ucia (Marmolejo), se ha identificado con un paraje situado a unos cuatro kilómetros del actual casco urbano de Villanueva, conocido como Vega Baja. 

En época musulmana fue una pequeña alquería, que tras la conquista de esta comarca fue entregada por Alfonso X a la ciudad de Andújar. 

Durante el siglo XV Villanueva fue escenario de las luchas de los partidarios de Enrique IV, capitaneados por el Condestable don Miguel Lucas de Iranzo, y la nobleza levantisca. En Villanueva tuvo lugar la batalla de San Bernabé, en la que al volver los de Andújar de su batalla contra don Juan de la Cueva en Baeza, capitaneada por el Condestable Iranzo, fueron sorprendidos en Villanueva por don Fabrique y los de Córdoba con 500 caballos y 800 infantes. Entre otros hechos, aquí se refugiaron los Palomino de Andújar, que estaban en contra de la política que llevaba el alcalde de esta ciudad, Pedro Escavias, unido a las armas del Condestable Lucas de Iranzo. 

En 1605 el obispo don Sáncho Dávila y Toledo bendecía el nuevo templo parroquial, erigido por la fundación de doña María Jiménez de Lara, abuela del célebre historiador Ximena Jurado. 

Poco después de esta fundación tuvo lugar el proceso de beatificación de Santa Potenciana, uno de los acontecimientos más importantes en la historia de Villanueva. Esta santa, que vivió en época mozárabe, era tejedora e hizo una vida eremética. Su martirio consistió en emparedamiento. El sepulcro, situado en la ribera septentrional del río Guadalquivir, era visitado por gentes de Villanueva y Andújar para pedir su intercesión. En 1628 el obispo Moscoso y Sandoval ordenó abrir el sepulcro e inició un proceso sobre los milagros de esta santa, que culminó diez años después cuando fue elevada a los altares por Urbano VIII. 

Durante la invasión francesa una fuerte división del general Dupont tomó Villanueva con objeto de cortar el cuerpo de Reding que se hallaba en Mengíbar. En aquel punto se celebró una cruenta batalla que hizo que las tropas españolas retrocediesen. Poco después, el General Castaños organizaría en su término la columna que vencería en la batalla de Bailén. 

La antigua Villanueva de Andújar se segregó como lugar de esta ciudad en 1792 y tomó el nombre de Villanueva de la Reina.