Com el seu nom indica, el palau de l'Almudaina va ser originalment una ciudadela feta construir pels geovernants àrabs fora de les muralles, prop de la ciutat, amb el baluart que domina la badia de Palma. Poseeix una sòlida muralla visible encara i al seu interior sorgeix un edifici rectangular amb 5 torres almenades.

Jaume II, cuya cort es trobava oficialment a Perpinyà, el va emprar com a residència d'estiu, encarregant la seva reconstrucció a Pere Salvà, el mateix que va dirigir la construcció del castell de Bellver. Jaume II va modificar notablement aquesta palau, afegint a la solidesa musulmana de la seva construcció, la riquesa i comoditats desitjades per a la cort Mallorquina.
Va ser, per tant, a partir del 1309 quan s'iniciaren els treballs de reconstrucció durant els quals s'afegiren 4 torreons almenats, un pòrtic i a la fatxada del mar una fina galeria ojival.. El sobirà mallorquí va fer construir també una Capella Reial anomenada també de Sta. Ana : d'estil gòtic i de petites dimensions però molt bella; té un portal romànic al seu interior és important un retable pintat al 1465 pel mallorquí Rafael Mojer. Visible des de lluny, sobre una de les 4 torres hi ha una veleta representant un àngel.
El palau de l'Almudaina és actualment sede de la capitania general de balears i moltes obres d'art hi són a ell: tapissos flamencs del segle XVI i XVII quan es representaven els fets històrics d'Espanya entre moltes altres obres.
Darrera del palau i sota les muralles hi són els cèlebres jardins nomenats "S'hort del Rei" amb precioses fonts amb canons d'aigua i d'una composició plàstica que el cèlebre escultor Alexander Calder va donar a la ciutat de Palma.