Throughout the past few years, a lively debate emerged about the timing and magnitude of the human migrations between the Iberian Peninsula and the Maghreb. Several pieces of evidence, including archaeological, anthropological, historical, and genetic data, have pointed to a complex and intermingled evolutionary history in the western Mediterranean area. To study to what extent connections across the Strait of Gibraltar and surrounding areas have shaped the present-day genomic diversity of its populations, we have performed a screening of 2.5 million single-nucleotide polymorphisms in 142 samples from southern Spain, southern Portugal, and Morocco. We built comprehensive data sets of the studied area and we implemented multistep bioinformatic approaches to assess population structure, demographic histories, and admixture dynamics. Both local and global ancestry inference showed an internal substructure in the Iberian Peninsula, mainly linked to a differential African ancestry. Western Iberia, from southern Portugal to Galicia, constituted an independent cluster within Iberia characterized by an enriched African genomic input. Migration time modeling showed recent historic dates for the admixture events occurring both in Iberia and in the North of Africa. However, an integrative vision of both paleogenomic and modern DNA data allowed us to detect chronological transitions and population turnovers that could be the result of transcontinental migrations dating back from Neolithic times. The present contribution aimed to fill the gaps in the modern human genomic record of a key geographic area, where the Mediterranean and the Atlantic come together.