La primitiva muralla debió construirse en la primera mitad del siglo IX englobando todo el núcleo urbano y uniendo las fortificaciones del Castillo Mayor, el Castillo de la Torre Mocha, el Castillo de Doña Martina y el Castillo Real, y posiblemente aislado el Castillo de la Peña como punto fuerte avanzado (albarrana).