The trans-Saharan gold and salt trade as well as the trans-Saharan slave trade played an important role in population movements connecting sub-Saharan and Mediterranean economies during the Middle Ages. The slave trade alone is said to have transported more than 9 million slave soldiers and domestic servants along the trans-Saharan route. In this study, we present the genomic analysis of two human individuals from a cave site in the area of present-day Morocco which were directly dated to the Medieval period. The samples were processed in a designated ancient DNA lab and the genomic data obtained shows standard patterns of authentic ancient DNA with low levels of contamination. Both individuals – which represent the first ancient genome sequence data from North Africa – do not exhibit particular genetic affinities to modern North Africans or any other present-day population in published genotype data sets despite relatively extensive data has been produced from many areas of Africa. In fact, the most parsimonious way to model them genetically is as two-source admixture between Mediterranean Europeans and Southern Africans. The lack of archaeological context of the two individuals opens up various alternatives to explain their genomic pattern. Both individuals could represent a Medieval African population without population continuity to modern-day populations. Alternatively, both Mediterranean Europe and Southern Africa are known source regions in the Arab slave trade, thus they could potentially represent the offspring of slaves of different origin. The Arab slave trade extended over a longer period and may have involved more slaves than its transatlantic counterpart and our data might provide the first genetic insight into this historical process and the people who suffered in it. Our results highlight how archaeogenetic research can shed lights into historical events and long-distance population movements while opening new questions for the interpretation of the data.