The Iberian peninsula is a peripheral region of Europe in close proximity to Africa. Its inhabitants have an overall mtDNA genetic landscape typical of European background, although with signs of some African influence, whose features we deemed to disclose by analyzing available mtDNA HVRI distributions and new data. We analyzed 1,045 sequences. The most relevant results are the following: (1) North African sequences (haplogroup U6) present an overall frequency of 2.39%, and sub-Saharan sequences reach 3.83%, values that are, in both cases, much higher than those generally observed in Europe; and (2) there is a substantial geographic heterogeneity in the distribution of these lineages (haplogroup L being the most frequent in the south, whereas haplogroup U6 is generally more common in the north). The analysis of the observed diversity within each haplogroup strongly suggests that both were recently introduced (in historical times). Although for haplogroup U6 the documented event that is demographically compatible is the Islamic period (beginning of the 8th century to the end of the 15th century), for haplogroup L the most probable origin is the modern slave trade (mid 15th century to the end of the 18th century). However, the observed geographic structuring for one of the haplogroups does not fit the expected distribution provided by simplistic historical considerations. In fact, although for haplogroup L the north-south increasing frequency is corroborated by historical data, the opposite trend, observed for haplogroup U6, is more difficult to reconcile with the magnitude and time span of the Islamic political and cultural influence, which lasted longer and was more intense in the south. To clarify this conundrum, we need not only a substantial increase in the amount of mtDNA data (particularly for North Africa) but also new historical data and interpretations.