A últimos del siglo VII los musulmanes arrebatan a Bizancio el norte de África. Las Baleares quedan entonces sin más defensa que sus propios medios y no tardan en sucumbir ante la fuerza de la expansión islamita. Los árabes efectuaban contra Menorca frecuentes "razzias": se llevaban cautivos, incendiaban predios costeros, quizá asediaban temporalmente una población. Esta situación angustiosa duró por espacio de dos siglos.
Los "Annales Regni Francorum" afirman que en 798 desde Baleares se solicitó la protección de Carlomagno, quien ordenó en consecuencia a la represión de las piraterías de los árabes. Pero la inclusión de estas islas en el Imperio franco sería más bien teórica.
Durante el siglo IX el Mediterráneo occidental aparece afectado de una gran inseguridad. Las naves del condado de Ampurias, las de Al-Andalus y las de los Normándose interfieren en sus relaciones con las Baleares. Abderramán II por el año 849 dirigió hacia estas islas una expedición de castigo por haber quebrantado sus habitantes un pacto al atacar a unas naves musulmanas ancladas en sus costas. Este hecho así como el apoyo prestado anteriormente a la escuadra de Ampurias nos indican que los baleáricos se sentían ligados a las potencias cristianas en sus luchas con los islamitas.
Según el crónico de Sebastián de Salamanca en el año 859 los Normandos atacaron a Mallorca, Menorca y Formentera, en las que debieron causar grandes estragos, dejándolas muy despobladas. La destrucción violenta de las basílicas paleocristianas fue debida probablemente a la invasión normanda y el estado de despoblación y ruina en que quedaron las Baleares explica que según una bula del Papa Romano del año 898, aparezcan las iglesias de estas islas bajo la jurisdicción del Obispo de Girona.
A principios del siglo X (902-903) las Baleares fueron conquistadas e incorporadas al Califato de Córdoba. En 1045 después de la escisión del estado musulmán español quedaron incorporadas al reino taifa de Denia y desde 1087 gozaron de independencia. En 1114 tuvo lugar una efímera invasión conjunta de písanos y catalanes, que llegó a conquistar este reino pero provocó la intervención y el dominio de los Almorávides que aún después de vencidos en Al-Andalus, lograron mantenerse en las Baleares con la dinastía de los Ganiya hasta que finalmente en 1203 fueron suplantados por los Almohades.
Los islamitas llamaban a nuestra isla "Menurka". La antigua Jammona (Ciudadela) fue desde entonces la capital de la isla: la "Medina-Menurka". En ella residía el almojarife o gobernador, en un edificio que daba sobre el puerto de Ciudadela, el mismo lugar donde estuvo después el palacio del gobernador y actualmente la Casa-Ayuntamiento.
Los musulmanes dividieron la isla en cuatro distritos, gobernados por sendos "sahibs" o prefectos: Hasmaljuda (Torrellafuda), Bini-Saida, Binifabini y Alscaions. La "Medina-Minurka" y la actual Mahón estaban fortificadas; pero la principal defensa árabe era el castillo roquero de "Sent-Agáyz", en la colina de Santa Águeda; la gobernaba un "kaid" o alcaide.
Pocos restos arqueológicos subsisten en Menorca de esta época: la parte baja del campanario de la Catedral en Ciudadela, antiguo alminarete de la mezquita que, al derribarse esta para construir el actual templo, se dejó para convertirlo en campanario; presenta en su interior el detalle, bien arabizante, de una cuesta en lugar de escalera. Parece ser un resto de la época musulmana el callejón cubierto de arcos llamado "Es Pont d'Es General", en Mahón.
Indudablemente hay parte musulmana en las murallas del castillo de Santa Águeda, pero está en estado tan ruinoso que no resulta posible distinguirla de las construidas en época romana y en la medieval.
Poco después de ser conquistada Mallorca por Jaume I de Aragón en 1229 Menorca fue hecha tributaria. Era imposible una resistencia armada, por parte de los musulmanes menorquines, que se avinieron a pactar con el rey de Aragón. Este se hallaba de nuevo en Mallorca en 1232 realizando una campaña para someter a los moros que habían quedado en las montañas.
Como cuenta la Crónica del rey Jaume I, desde Mallorca envió una embajada a Menorca compuesta por Berenguer de Santa Eugenia, don Assalid de Gudar y Ramón de Serra, comendador de los caballeros templarios, con el fin de obtener la sumisión de esta isla. Llegaron a Ciudadela en tres naves, fueron bien recibidos y agasajados y al exponer sus pretensiones los moros les suplicaron que aguardasen hasta el día siguiente para dar su respuesta.
Al atardecer el rey estaba en las costas de Capdepera, que está enfrente a Menorca, con unos pocos hombres a su servicio. El rey hizo encender unas fogatas que desde Menorca parecían un gran ejército. Los moros de Menorca, atemorizados ante el inminente peligro de una ocupación guerrera, se avinieron en hacerse tributarios del rey de Aragón.
Además de los tributos anuales que tenían que pagar los musulmanes menorquines al reino de Aragón, los aragoneses adquirían el derecho de estar en Ciudadela y en "la colina donde está el castillo mayor de la isla" (Santa Águeda).
En esta Crónica Real de Jaume I, vemos consignado por primera vez, el nombre de Ciutadella. Parece que no tiene aquí el significado de "Ciudad amurallada (Ciudadela)", aunque ya entonces lo era la antigua capital musulmana; sino que Ciutadella es un diminutivo de "Ciutat", sugerido en cierta manera por ser la Ciudad de la isla y en paralelismo con la denominación de la capital de la isla hermana: "Ciutat de Mallorca, Ciutadella de Menorca."