Historically fragmented and specialised habitats such as granite outcrops are understudied globally unique hotspots of plant evolution. In contrast to predictions based on mainstream population genetics theory, some granite outcrop plants appear to have persisted as very small populations despite prolonged geographic and genetic isolation. Eucalyptus caesia Benth. is a long-lived lignotuberous tree endemic with a naturally fragmented distribution on granite outcrops in south-western Australia. To quantify population to landscape level genetic structure we employed microsatellite genotyping at 14 loci of all plants in 18 stands of E. caesia. Sampled stands were characterised by low levels of genetic diversity, small absolute population sizes, localised clonality and strong fine-scale genetic sub-division. There was no significant relationship between population size and levels of heterozygosity. At the landscape scale, high levels of population genetic differentiation were most pronounced among representatives of the two subspecies in E. caesia as originally circumscribed. Past genetic interconnection was evident between some geographical neighbours separated by up to 20 kilometres. Paradoxically, other pairs of neighbouring stands as little as 7 kilometres apart were genetically distinct. There was no consistent pattern of isolation by distance across the 280 km range of E. caesia. Low levels of gene flow, together with strong drift within stands, provides some explanation of the patterns of genetic differentiation we observed. Individual genet longevity via the ability to repeatedly re-sprout and expand from a lignotuber may enhance the persistence of some woody perennial endemic plants despite small population size, minimal genetic interconnection and low heterozygosity.