La fortaleza de la plaza existiba ya en lo sieglo X. Seguntes lo cheografo andalusí Al-Udri lo mesmo califa Abderramán III acampó baixo los muros de lo castiello de Maluenda. Esto se desvinió en una campanya de castigo contra lo rebel Muhammad al-Tuchibí de Zaragoza entre los anyos 933 y 934, y dimpués en 937 quan la defendeba lo mesmo Muhammad al-Tuchibí y lo exercito califal la habió d'ocupar pa cutio.