Del seu recinte, quasi rectangular, se'n veuen trossos encara, especialment a la torre més alta, que, des del segle XIV, és anomenada la torre de l’Àngel. Després de la conquesta de l’illa (1229), l’edifici fou retocat i arranjat, per tal de fer-ne una residència reial: Jaume II, des del 1305 fins al 1313, hi feu obres, i transformà tota la torre de la fortalesa musulmana en departament personal del rei. L’any 1337 hi fou afegit un oratori anomenat la capelleta del Mirador. De l’edifici actual, dit el Palau de l’Almudaina, el més característic és, a part el recinte amb les torres, que han estat molt modificades, la façana de migdia, amb les seves torres laterals quadrades i les arcuacions gòtiques, i el gran pati principal (anomenat pati del Rei), amb nombroses restes gòtiques i el portal de la capella reial de Santa Anna, que conserva un timpà amb escultures del segle XIV. És especialment notable aquesta capella del comerçament del segle XIV, que reprodueix les característiques de la capella de la Santa Creu de Perpinyà: nau de dos trasts i un presbiteri quadrat, que, a una certa altura, es transforma en pentàgon per mitjà de trompes d’angle. L’interior fou enriquit amb un retaule de Ramon Destorrents, conservat en petita part. L’edifici, objecte d’una transformació exagerada al començament del segle XX, fou finalment restaurat amb bon criteri. Durant molts d’anys els locals de l’Almudaina han estat ocupats per l’audiència territorial, per la capitania general i d’altres organismes militars.