Abstract Background A proportion of 1/4 to 1/2 of North African female pool is made of typical sub-Saharan lineages, in higher frequencies as geographic proximity to sub-Saharan Africa increases. The Sahara was a strong geographical barrier against gene flow, at least since 5,000 years ago, when desertification affected a larger region, but the Arab trans-Saharan slave trade could have facilitate enormously this migration of lineages. Till now, the genetic consequences of these forced trans-Saharan movements of people have not been ascertained. Results The distribution of the main L haplogroups in North Africa clearly reflects the known trans-Saharan slave routes: West is dominated by L1b, L2b, L2c, L2d, L3b and L3d; the Center by L3e and some L3f and L3w; the East by L0a, L3h, L3i, L3x and, in common with the Center, L3f and L3w; while, L2a is almost everywhere. Ages for the haplogroups observed in both sides of the Saharan desert testify the recent origin (holocenic) of these haplogroups in sub-Saharan Africa, claiming a recent introduction in North Africa, further strengthened by the no detection of local expansions. Conclusions The interpolation analyses and complete sequencing of present mtDNA sub-Saharan lineages observed in North Africa support the genetic impact of recent trans-Saharan migrations, namely the slave trade initiated by the Arab conquest of North Africa in the seventh century. Sub-Saharan people did not leave traces in the North African maternal gene pool for the time of its settlement, some 40,000 years ago.