La historiografía más antigua (siglo ) afirmaba que fue levantada entre 1090 y 1099 —prácticamente inmediata a la "reconquista" cristiana de la ciudad— sobre muros con pasado romano, visigodo y musulmán, atribuyéndola un origen mítico, al ser supuestamente construida en sus orígenes por Alcideo, hijo de Hércules.