Thanks to the ability to digest lactose, Arabian nomads had become less dependent upon their sedentary neighbors and some of these populations spread to Africa. When and by which route they migrated to their current locations have previously been addressed only by historical and archaeological data. To address the question of Arab expansion into Africa, we collected samples from several Arabic populations, especially the Baggara in Chad and Sudan. We analyzed mutations associated with lactase persistence and reconstructed the surrounding haplotypes defined by SNP polymorphisms. We also sequenced their mitochondrial DNA to investigate relative proportions of sub-Saharan and Eurasian origins. We estimated the expansion age of the -13,915*G mutation in four different Arabian datasets. The oldest age was identified in Yemen (1,356-1,799 ya) and the youngest in a Sudanese group of Rashaayda Arabs (219-312 ya). We also found a negative correlation between the frequency of the -13,915*G allele and the frequency of sub-Saharan mtDNA haplotypes. Even if the age of the most recent common ancestor of -13,915*G is ∼4 ka as shown in a previous study, our results suggest that its spread to Africa was more recent, which is consistent with the migrations of Arabic tribes. Because the incidence of sub-Saharan mtDNA haplotypes is negatively correlated with the occurrence of -13,915*G, we suggest that the decrease of its frequency in Africa has been caused by progressive admixture of the Arabian nomads with sub-Saharan populations.