Entre los años 713 y 714, poco después de la llegada del ejército de Táriq ibn Ziyad a la península ibérica, el emir Abd al-Aziz ibn Musa ocupó las tierras valencianas. Los musulmanes las denominaron Xarq al-Ándalus, es decir, la tierra situada en el Levante de al-Ándalus.

La mayor parte de la conquista musulmana de la península se llevó cabo mediante tratados, como el llamado pacto de Teodomiro (Tudmir para los árabes), un noble visigodo y señor de extensas tierras en torno a Orihuela. Teodomino reconoció la soberanía musulmana y se avino a pagar tributos a cambio de mantener sus propiedades.

Durante los siglos VIII, IX y X, Xarq al-Ándalus fue gobernada por valíes dependientes del Califa de Córdoba. A principios del siglo XI, cuando el califato se disgregó en pequeños reinos independientes (taifas), en Xarq al-Ándalus se crearon las taifas de Denia y Valencia.

Posteriormente, estos reinos de taifas valencianos ampliaron o redujeron su territorio en continuos enfrentamientos con las taifas vecinas. En estas luchas internas, los reyes de las taifas contrataban los servicios de guerreros como Rodrigo Díaz de Vivar, que acabó conquistando la ciudad de Valencia.

Tras la incorporación a al-Ándalus, la mayoría de la población cristiana (mozárabes) se convirtió al islam (muladíes) y adoptó la lengua y los modos de vida propios de la sociedad islámica. También se instalaron en Xarq al-Ándalus un gran número de árabes y, sobre todo, de bereberes procedentes del norte de África.

Xarq al-Ándalus estuvo integrada en el mundo islámico durante casi cinco siglos, hasta que en la primera mitad del siglo XIII fue conquistada por Jaime I de Aragón.