The identification of past glacial refugia has become a key topic for conservation under environmental change, since they contribute importantly to shaping current patterns of biodiversity. However, little attention has been paid so far to interglacial refugia despite their key role for the survival of relict species currently occurring in climate refugia. Here, we focus on the genetic consequences of range contraction on the relict populations of the evergreen shrub Myrtus nivellei, endemic in the Saharan mountains since at least the end of the last Green Sahara period, around 5.5 ka B.P. Multilocus genotypes (nuclear microsatellites and AFLP) were obtained from 215 individuals collected from 23 wadis (temporary rivers) in the three main mountain ranges in southern Algeria (the Hoggar, Tassili n'Ajjer and Tassili n'Immidir ranges). Identical genotypes were found in several plants growing far apart within the same wadis, a pattern taken as evidence of clonality. Multivariate analyses and Bayesian clustering revealed that genetic diversity was mainly structured among the mountain ranges, while low isolation by distance was observed within each mountain range. The range contraction induced by the last episode of aridification has likely increased the genetic isolation of the populations of M. nivellei, without greatly affecting the genetic diversity of the species as a whole. The pattern of genetic diversity observed here suggests that high connectivity may have prevailed during humid periods, which is consistent with recent paleoenvironmental reconstructions.