Villavieja ha sido un yacimiento prehistórico totalmente desconocido para la investigación hasta su descubrimiento en el siglo XXI.

No obstante, su muralla era reconocida desde el siglo XIX. Así, el geógrafo Pascual Madoz cita en su diccionario que:

…el tajo denominado Villavieja, inmediato a la población de Fuentes de Cesna a la parte E. a cuya cima no puede subirse por las escarpaduras que presenta, sino por una colina o cord. sit. al N. Por los vestigios que dicha esplanada se encuentran, se sospecha debieron existir edificios, pero no hay documento alguno que indique la época;…(MADOZ, 1845: tomo I, voz Algarinejo).

Y sin embargo, a pesar de esta temprana referencia, el lugar guardó el misterio de sus piedras, permaneciendo oculto y desconocido para la investigación de la Prehistoria Reciente del sur de la península Ibérica.