Entre el 455 i el 534 l’illa va formar part del Regne vàndal, tribu germànica que formà un ampli imperi marítim a la Mediterrània occidental. Ja el 425 havien desembarcat a l’illa, la saquejaren i destruïren Pollentia, capital administrativa i el nucli urbà més important. A partir de l’ any 534, Mallorca entrà a formar part de l’ Imperi bizantí.
Justinià I (527-565) emperador de l’Imperi romà d’Orient emprèn l’expansió per tot el Mediterrani, i Apol·linar, general bizantí, conquereix les illes i les inclou en aquest imperi.
Tanmateix després de l’expulsió dels bizantins de la península i del nord d’Àfrica, Mallorca quedà aïllada i perd tot l’interès del llunyà Imperi d’Orient. Per tant entre el 698 i 903, les Illes Balears formaven part de l’Imperi bizantí, però en la pràctica gaudiren d’una gran independència política i administrativa.
Durant aquests anys les petites comunitats cristianes mallorquines reberen nombrosos atacs dels musulmans i dels normands, que sumeixen Mallorca en una profunda crisi.
L’any 903 es produeix la incorporació de Mallorca al món islàmic després d’una ràpida conquesta que només topà amb la resistència dels cristians al voltant d’alguns castells, com el d’Alaró, on resistiren més de vuit anys. Passen a ser les Illes Orientals d’al-Andalus i el seu conqueridor es converteix en el valí o governador que encetà una política de reconstrucció, afavorint la immigració de musulmans de la península, refent el camp i la ciutat, reorganitzant el comerç, etc.
Mallorca restà sota el domini de Còrdova que emprava la flota i la situació geogràfica illenca per realitzar incursions cap al Mediterrani cristià del nord. Després d’una etapa d’esplendor l’emirat d’al-Andalus entrà en crisi i es desmembrà sorgint els petits regnes taifes, més febles davant els atacs dels cristians del nord, però amb un alt nivell cultural i econòmic. D’aquesta manera l’any 1015 Mallorca passà a dependre de la taifa de Dènia (a l’actual País Valencià) fins que el 1086 aprofità la crisi de la taifa de Dènia per aconseguir una independència precària, marcada per la falta d’aliments, que abocaven els illencs a la pirateria per sobreviure, cosa que va provocar una croada pisanocatalana que saquejà i destruí Medina Mayurca (l’actual Palma de Mallorca) l’any 1115.
Entre els segles X i XIII es desenvolupà a Mallorca una rica agricultura de regadiu, es construïren sínies, fonts, canals, etc. El camp estava dividit en alqueries explotades per un clan familiar de forma col·lectiva. A Medina Mayurca, es concentraven els artesans, els comerciants, les classes dirigents i l´administració de l´illa. La vida cultural i artística també va florir i Mallorca es va convertir en un centre d´intercanvi entre l´orient i l´occident, entre el món musulmà i el cristià.