North African populations are considered genetically closer to Eurasians than to sub-Saharans. However, they display a considerably high mtDNA heterogeneity among them, namely in the frequencies of the U6, East African, and sub-Saharan haplogroups. In this study, we describe and compare the female gene pools of two neighboring Tunisian populations, Kesra (Berber) and Zriba (non-Berber), which have contrasting historical backgrounds. Both populations presented lower diversity values than those observed for other North African populations, and they were the only populations not showing significant negative Fu's Fs values. Kesra displayed a much higher proportion of typical sub-Saharan haplotypes (49%, including 4.2% of M1 haplogroup) than Zriba (8%). With respect to U6 sequences, frequencies were low (2% in Kesra and 8% in Zriba), and all belonged to the subhaplogroup U6a. An analysis of these data in the context of North Africa reveals that the emerging picture is complex, because Zriba would match the profile of a Berber Moroccan population, whereas Kesra, which shows twice the frequency of sub-Saharan lineages normally observed in northern coastal populations, would match a western Saharan population except for the low U6 frequency. The North African patchy mtDNA landscape has no parallel in other regions of the world and increasing the number of sampled populations has not been accompanied by any substantial increase in our understanding of its phylogeography. Available data up to now rely on sampling small, scattered populations, although they are carefully characterized in terms of their ethnic, linguistic, and historical backgrounds. It is therefore doubtful that this picture truly represents the complex historical demography of the region rather than being just the result of the type of samplings performed so far.