Erica australis and Erica arborea are morphologically and ecologically similar heather species. Erica australis is restricted to the western Mediterranean Basin where it overlaps with the westernmost distribution of E. arborea. Here we investigate the role of the Strait of Gibraltar (SG) as a potential biogeographical barrier to dispersal and/or as glacial refugium in these two Erica spp. in the western Mediterranean (WMed) region with contrasting geographical origins and distributions. Samples were collected from 55 and 54 populations of E. australis and E. arborea, respectively. One individual each of 52 and 45 populations of E. australis and E. arborea, respectively, were sequenced for plastid DNA regions, and 1304 and 1214 individuals from 44 and 42 populations of E. australis and E. arborea, respectively, were genotyped using nuclear microsatellites (SSRs). Plastid DNA sequences were used to estimate divergence time of lineages and to construct haplotype networks. SSR data helped to infer population genetic diversity and fixation indices and genetic structure patterns through Bayesian analysis, analysis of molecular variance and isolation by distance. Plastid haplotype diversity of E. australis was higher in the SG than in the WMed area, whereas the opposite was found in E. arborea. SSRs revealed high genetic diversity within populations of both species and population genetic structure patterns were consistent with those retrieved from plastid DNA. The SG was identified as the likely area of origin and diversification for E. australis in the late Pliocene-Pleistocene, where it survived the Last Glacial Maximum (LGM) and expanded northwards into the western Iberian Peninsula. In contrast, two separate evolutionary lineages were found for E. arborea in the Iberian Peninsula. The SG and southern WMed areas represent the western Mediterranean expansion limit of an E. arborea lineage from East Africa/Arabia in the late Pliocene-Pleistocene, whereas the northern WMed populations were relicts from an older refugium that survived LGM in north-western Iberia. This study illustrates how geographical range and origin explain differences in the phylogeographical structure of co-distributed Mediterranean plants and highlights the role of the SG as a Pleistocene refugium and biogeographical crossroads in the Mediterranean.