Antiguamente Villanueva era una aldea llamada “La Moraleja”. Tenía pocos habitantes pero que iban progresando poco a poco. Llegaron a hablar con el Arzobispo de Toledo, D. Pedro Tenorio. Este intercedió ante el rey Enrique III, quien concedió el título de Villa el 8 de Septiembre de 1396.
¿Por qué el municipio fue llamado Villanueva del Arzobispo? Villa por el título otorgado, Nueva porque hasta este momento no existía como tal y del Arzobispo en honor a D. Pedro Tenorio, Arzobispo de Toledo.
Se le concedieron todos los privilegios que se podían tener en aquel momento: Mercado, policía, ausencia del pago de impuestos a Iznatoraf, etc. Incluso, Villanueva tuvo su propio escudo caracterizado por un león y la imagen de la Virgen de la Fuensanta. El león era parte del escudo propio del Arzobispo de Toledo y la imagen de la Virgen por la gran devoción que los locales le procedían.
Dentro de las obligaciones de la villa, estuvieron la de levantar una muralla con una Puerta Alamina y una Puerta Arquillo.
Con anterioridad la localidad se llamaba Moraleja, pertenecía a Iznatoraf y desde principios del siglo XIII formaba parte del Adelantamiento de Cazorla. Anteriormente, los árabes de Iznatoraf la eligieron como zona de expansión de ocio, donde se organizaban carreras de caballos, y los artesanos instalaron sus talleres en Al-Buxaressa. Existen indicios fundamentados en el antiguo nombre de la localidad, que antes de ser llamada La Moraleja fue denominada Al-Buxaressa por los árabes, de ahí proviene el nombre de “La Moraleja”.
Más tarde Villanueva fue avanzando y es Felipe II quién le concedió la jurisdicción criminal en el año 1573. Ya en el año 1920 el rey Alfonso XIII le concede el Título de Ciudad a Villanueva del Arzobispo.
La Carta Fundacional llegó a Vva. Del Arzobispo en 1958. Lamentablemente más tarde este documento se extravió debido a la Guerra Civil, a principios del siglo XIX durante la guerra contra el invasor francés, nuestro pueblo fue refugio de guerrilleros que acosaron continuamente el paso de las tropas napoleónicas. Como consecuencia de estas actividades se produjeron diversos daños en los conventos y entre otras consecuencias la pérdida de nuestra Carta.
Afortunada y sorprendentemente, pasados muchos años apareció en Linares. Una mujer llamada Carmen Artiaga, maestra de profesión, encontró tal documento y lo donó a nuestro pueblo. La Carta fue restaurada y se encuentra desde entonces en el Ayuntamiento a buen recaudo ya que es el documento más antiguo que poseemos.