Ibiza, an island in present-day Spain, was conquered in 902 CE by the Umayyad Emirate of Córdoba. The island remained under Islamic rule until 1235. Here, we analyse the genetic and metagenomic profiles of 13 individuals from an Islamic cemetery in Ibiza, dated to 950–1150 CE. Genome-wide analyses reveal heterogeneity, with ancestry components from Europe, North Africa, and Sub-Saharan Africa. Our analyses estimate that North African gene flow occurred two to seven generations before these individuals lived, suggesting admixture following the Islamic conquest of Iberia and potentially on Ibiza itself. Notably, two individuals trace their Sub-Saharan origins to distinct regions, Senegambia and present-day southern Chad, providing direct evidence of trans-Saharan connections via military and slave networks documented in contemporary Arabic sources. Metagenomic analyses detect several pathogens in this community, with one individual carrying Mycobacterium leprae, offering insight into the presence of leprosy in Ibiza. Our findings align with the historically documented two-pulse demographic model, indicating an initial settlement following the early tenth-century conquest and a second influx associated with Almoravid movements in the twelfth century. These securely dated genomes offer insights into medieval population dynamics and health in the Balearics.