Many habitat specialist species are originally composed of small, discontinuous populations because their habitats are naturally fragmented or patchy. They may have suffered the long-term effects of natural patchiness. Mediterranean heathlands, a representative habitat in the Strait of Gibraltar region, are associated with nutrient-poor, acidic sandstone soils. Sandstone soil patches in the African side of the Strait (Tangier) are, in general, smaller and more scattered than in the European side (Algeciras). In this study, we analyze the effect of this sandstone patchiness on the population genetic diversity and structure of two Erica species from these Mediterranean heathlands that differ in their edaphic specificity, E. australis, sandstone specialist, and E. arborea, generalist. Average levels of within-population genetic diversity and gene flow between populations were significantly lower in Tangier (high sandstone patchiness) than in Algeciras (low patchiness) for the sandstone specialist, whereas no differences between both sides of the Strait were detected in the edaphic generalist. Since most endemic species in Mediterranean heathlands of the Strait of Gibraltar are sandstone specialists, these results highlight an increased vulnerability to loss of genetic diversity and local extinction of the heathland endemic flora in the Tangier side of the Strait of Gibraltar.