Being at the Western fringe of Europe, Iberia had a peculiar prehistory and a complex pattern of Neolithization. A few studies, all based on modern populations, reported the presence of DNA of likely African origin in this region, generally concluding it was the result of recent gene flow, probably during the Islamic period. Here we provide evidence of much older gene flow from Africa to Iberia by sequencing whole genomes from four human remains from Northern Portugal and Southern Spain dated around 4,000 years BP (from the Middle Neolithic to the Bronze Age). We found one of them to carry an unequivocal Sub-Saharan mitogenome of most likely West or West-Central African origin, never reported before in prehistoric remains outside Africa. Our analyses of ancient nuclear genomes show small but significant levels of Sub-Saharan African affinity in several ancient Iberian samples, which indicates that what we detected was not an occasional individual phenomenon, but an admixture event recognizable at the population level. We interpret this result as evidence of an early migration process from Africa into the Iberian Peninsula through a Western route, possibly across the Strait of Gibraltar.