Entre 455 y 534 la isla afrontó parte del Reino vándalo, tribu germánica que formó un amplio imperio marítimo en el Mediterráneo occidental. Ya en el 425 habían desembarcado en la isla, la saquearon y destruyeron Pollentia, capital administrativa y el núcleo urbano más importante. A partir del año 534, Mallorca entró a formar parte del Imperio Bizantino.

Justiniano I (527-565) emperador del Imperio romano de Oriente emprende la expansión por todo el Mediterráneo, y Apolinar, general bizantino, conquista las islas y las incluye en este imperio. De todos modos después de la expulsión de los bizantinos de la península y del norte de África, Mallorca quedó aislada y perdió todo el interés del lejano Imperio de Oriente. Por tanto entre 698 y 903, las Islas Baleares formaban parte del Imperio bizantino, pero en la práctica disfrutaron de una gran independencia política y administrativa. Durante estos años las pequeñas comunidades cristianas mallorquinas recibieron numerosos ataques de los musulmanes y de los normandos, que sumergen a Mallorca en una profunda crisis.

El año 903 se produce la incorporación de Mallorca en el mundo islámico después de una rápida conquista que sólo encontró la resistencia de los cristianos alrededor de algunos castillos, como el de Alaró, donde resistieron más de ocho años. Desde este momento empiezan a ser las Islas Orientales de al-Andalus y su conquistador se convierte en el valí o gobernador que inició una política de reconstrucción, favoreciendo la inmigración de musulmanes de la península, rehaciendo el campo y la ciudad, reorganizando el comercio, etc. Mallorca quedó bajo el dominio de Córdoba que utilizaba la flota y la situación geográfica isleña para realizar incursiones hacia el Mediterráneo cristiano del norte.

Después de una etapa de esplendor al-Andalus entró en crisis y se desmembró surgiendo los pequeños reinos taifas, más débiles ante los ataques de los cristianos del norte, pero con un alto nivel cultural y económico. De esta manera en 1015 Mallorca pasó a depender de la taifa de Denia (la actual País Valenciano) hasta que en 1086 aprovechó la crisis de la taifa de Denia para conseguir una independencia precaria, marcada por la falta de alimentos, que incitaban a los isleños a la piratería para poder sobrevivir, cosa que provocó una cruzada pisano catalana que saqueó y destruyó Medina Mayurca (la actual Ciudad de Mallorca) en 1115. Entre los siglos X y XIII se desarrolló en Mallorca una rica agricultura de regadío, se construyeron acequias, fuentes, canales, etc. El campo estaba dividido en alquerías explotadas por un clan familiar de forma colectiva. En Medina Mayurca, núcleo urbano principal, se concentraban los artesanos, los comerciantes, las clases dirigentes y la administración de la isla. La vida cultural y artística también floreció y Mallorca se convirtió en un centro de intercambio entre oriente y occidente, entre el mundo musulmán y el cristiano.