La zona estuvo habitada por antiguas civilizaciones como los tartéssicos, celtas y cartagineses. En los itinerarios de la antigua Bética ya estaba marcado este lugar como sitio de descanso y aprovisionamiento de las legiones romanas que desembarcaban en Ayamonte y se dirigían a Mérida. Fue llamado Lugar de los Castillejos por las pequeñas fortalezas o castilluelos que existían en sus contornos y que eran auxiliares de una principal llamada Praesidium, situada en la colina que hoy se denomina pie del castillo y que servía de defensa fronteriza y mansión militar. Durante la época feudal pasó a depender de la Casa de los Duques de Béjar, de la que se segregó al crearse el Marquesado de Gibraleón y asignársele éste como lugar de señorío. El 22 de julio de 1631 Su Majestad Felipe IV le concedió el título de villa, con la independencia, jurisdicción y prerrogativas correspondientes, llamándose desde entonces Villanueva de los Castillejos. La población del casco urbano de la población actual se inició en el s. XV. Durante la Guerra de la Independencia fue centro de aprovisionamiento de los ejércitos españoles y lugar de combate entre las tropas del General Ballesteros, comandante del Condado de Niebla, y la de los Generales franceses Gazán y Remoud.
El libro 'Expedientes carcelarios de Villanueva de las Cruces, Villanueva de los Castillejos y Villarrasa (Huelva). Prisión Provincial, 1936-1939' (Facediciones, 2008), de Juan José Antequera Luengo y Juan José Luengo Jiménez, da cuenta de cuantos vecinos sufrieron prisión durante la guerra civil española.