En este barrio palatino, se construyó en época califal un alcázar que todavía persiste aunque transformado.
Enfrente del alcázar se construyó la mezquita aljama, la más importante de la ciudad, que perduró hasta el siglo XV.
En el siglo XI se realizó una gran ampliación que dejó Sa Riera en el interior del nuevo recinto amurallado.
Este dio origen a una dinastía, los Banu Ganiya, que desde su capital en Madina Mayurqa intentaron reconquistar el imperio almorávide.
Al rey le tocó prácticamente toda la Vila d'Amunt, especialmente el barrio palatino de la Almudaina.
Construyeron iglesias y oratorios, de tal manera que en 1232 ya se hallaba dividida en cuatro parroquias.
A consecuencia del saqueo y las transformaciones quedan muy pocos restos visibles de Madina Mayurqa.
Los restos más importantes son el antiguo alcázar, los baños árabes y la puerta de la Almudaina.