La vila actual va sorgir en els primers anys del segle XV amb el nom de Encinaenana (a causa de la presència en aquest lloc d'aquesta planta arbòria). La seva fundació hauria estat deguda a vaquers de Pedroche (que van emigrar a causa de la pesta) establerts en ella des de començaments del segle xv. L'actual nom de Villanueva de Córdoba sorgeix a la fi del segle XV (1499), que segons J. Ocaña va poder ésser a causa del desig dels veïns de reafirmar la seva independència respecte als senyorius propers. Sembla que en alguns moments es coneix com a Villanueva de la Jara per la seva proximitat a la devesa del mateix nom. Villanueva de Còrdova va rebre de Carles I i de la seva mare Joana el títol de vila el 18 d'abril de 1533, sent la seva població d'aleshores de 280 veïns (1 veí = +/- 4 habitants).
