A variety of different methods are available for investigating the effects of past climate fluctuation on biota. Among them, molecular phylogeography and species distribution modeling approaches have been shown to be especially useful tools to trace past climate induced modifications of species’ geographic distributions. The results of both analytical approaches are here combined to better understand the influences of past climate changes on the fragmented distribution pattern of the lizard genus Iranolacerta that currently occurs in the northwest and central Zagros Mountains of Iran. While Iranolacerta zagrosica is restricted to few localities and cannot be modeled, the potential distribution of Iranolacerta brandtii suggested a large region of unfavorable habitat between northwest and the central Zagros Mountains populations. From the phylogenetic perspective, both species display deep genetic separation likely predating the Pleistocene. However, limited genetic diversity across this divided range of I. brandtii implies that the current separation is recent. Deeper genetic divergences were, nevertheless, uncovered within the northwest population. Since no recent geological events explain these results, the most likely explanation for such a distribution pattern is due to past climate fluctuations. Both sources of evidence suggest that during the early Holocene the northwest and Zagros populations of I. brandtii were connected, and the current pattern was shaped with their disconnection in the early Holocene. Further studies may identify potential glacial refugia for other species in this biodiverse region.