Our objective is to highlight the age of sub-Saharan gene flows in North Africa and particularly in Tunisia. Therefore we analyzed in a broad phylogeographic context sub-Saharan mtDNA haplogroups of Tunisian Berber populations considered representative of ancient settlement. More than 2,000 sequences were collected from the literature, and networks were constructed. The results show that the most ancient haplogroup is L3*, which would have been introduced to North Africa from eastern sub-Saharan populations around 20,000 years ago. Our results also point to a less ancient western sub-Saharan gene flow to Tunisia, including haplogroups L2a and L3b. This conclusion points to an ancient African gene flow to Tunisia before 20,000 BP. These findings parallel the more recent findings of both archaeology and linguistics on the prehistory of Africa. The present work suggests that sub-Saharan contributions to North Africa have experienced several complex population processes after the occupation of the region by anatomically modern humans. Our results reveal that Berber speakers have a foundational biogeographic root in Africa and that deep African lineages have continued to evolve in supra-Saharan Africa.