We recently learned that many of the typically East Eurasian mtDNA lineages present in Europe today arrived there during the Neolithic, and perhaps in some cases even the Mesolithic (see here and here). It now seems that a large part of the Sub-Saharan African mtDNA lineages found in Europe are also of Neolithic origin. However, most appear to have come "rather recently", as a result of contacts between Europe and Africa during the Roman Empire, the Trans-Atlantic slave trade, and so on.
Mitochondrial DNA (mtDNA) lineages of macro-haplogroup L (excluding the derived L3 branches M and N) represent the majority of the typical sub-Saharan mtDNA variability. In Europe, these mtDNAs account for <1% of the total but, when analyzed at the level of control region, they show no signals of having evolved within the European continent, an observation that is compatible with a recent arrival from the African continent. To further evaluate this issue, we analyzed 69 mitochondrial genomes belonging to various L sublineages from a wide range of European populations. Phylogeographic analyses showed that ∼65% of the European L lineages most likely arrived in rather recent historical times, including the Romanization period, the Arab conquest of the Iberian Peninsula and Sicily, and during the period of the Atlantic slave trade. However, the remaining 35% of L mtDNAs form European-specific subclades, revealing that there was gene flow from sub-Saharan Africa toward Europe as early as 11,000 yr ago.
Maria Cerezo et al., Reconstructing ancient mitochondrial DNA links between Africa and Europe, Published in Advance March 27, 2012, doi: 10.1101/gr.134452.111