Karališkieji Almudainos rūmai, esantys ant kranto, šalia katedros, yra seniausias pastatas Maljorkoje. Jo sienos iki šiol mena pirmąjį romėnų įtvirtinimą, pastatytą šioje vietoje 123 m. pr. Kr. Arabų laikotarpiu (X a. vidurys) romėnų griuvėsių vietoje buvo pastatyta citadelė – Valių arba saracėnų valdovo rezidencija, rekonkista vadinama „Zuda“. Aragono karūnai užkariavus Maljorką, tvirtovė buvo atstatyta karaliaus Jaime II įsakymu. Kaip pavyzdį pasiūlęs Perpinjano karališkųjų rūmų projektą, Jaime II patiki darbus architektui Pere Salva. Vykstant rekonstrukcijai, kuri prasidėjo 1281 m. ir tęsėsi iki 1343 m., Musulmonų rūmai įgavo keturis mūras, portiką ir elegantišką kolonadą fasade nuo jūros. Iš šono buvo pritvirtinta didžiulė vieno aukšto Sosto salė su aukštais gotikiniais skliautais. 1310 m. buvo pastatyta pagrindinė koplyčia. XVI amžiaus viduryje restauruojant sugriuvus Sosto salės skliautui, ji buvo padalinta į du aukštus.
Rūmų komplekso puošmena – senoviniai paveikslai, baldai, židiniai, XVI–XVII amžių flamandiški kilimai, karinė atributika. Vienoje iš salių išlikusios XIV amžiaus freskos.

Šiuo metu rūmus globoja Nacionalinis lobių fondas ir yra oficiali karališkosios šeimos vasaros rezidencija. Viename iš komplekso pastatų yra Balearų salų karinė komendantūra. Dauguma patalpų yra atviros visuomenei.