Many studies have tackled the existence of a genetic barrier in the Strait of Gibraltar between Iberian and North African populations, often with controversial conclusions. Here, we address this issue using a collection of Western Mediterranean populations and two dimensionality reduction methods: principal component analysis (PCA) and spatial PCA (sPCA). Our four different data sets consisted of (i) 16 polymorphic Alu insertions in 12 populations; (ii) 35 single-nucleotide polymorphisms in 13 populations; (iii) 13 short tandem repeats in 11 populations; and (iv) all 64 markers in 9 populations. In all PCA plots, South European and North African samples were visually distinguishable along the first PC. Several smaller clusters were also identifiable, especially on the African side of our geographical setting. sPCA indicated a single global structure for each of the marker sets and no local structures. These results are more compatible with a clinal distribution of allele frequencies rather than with abrupt changes, suggesting that isolation-by-distance, rather than a barrier to gene flow, is a more likely mechanism of genetic differentiation in the Western Mediterranean. An alternative/complementary explanation is progressive introgression from North African to Southwestern European populations.