The Oriental garden lizard (Calotes versicolor) is one of the few non-gekkonid lizards that are geographically widespread in the tropics. We investigated its population dynamics on Hainan Island and the adjacent mainland of China and Vietnam, focusing on the impact of cyclic upheaval and submergence of land bridges during the Pleistocene. Our Bayesian phylogenetic analysis reveals two mitochondrial lineages, A and B, which are estimated to have coalesced about 0.26 million years ago (95% credibility interval: 0.05-0.61 million years ago). Lineage A contains individuals mainly from central and southern Wuzhi Mountain on Hainan Island, whereas lineage B mainly comprises individuals from other sites on the island plus the adjacent mainland. The estimated coalescence times within lineages A (0.05 million years ago) and B (0.13 million years ago) fall within a period of cyclical land-bridge formation and disappearance in the Pleistocene. A spatial analysis of molecular variance identified two distinct population groupings: I, primarily containing lineage A, and II, mainly consisting of lineage B. However, haplotypes from lineages A and B occur sympatrically, suggesting that gene flow is ongoing. Neither Wuzhi Mountain nor Qiongzhou Strait and Gulf of Tonkin act as barriers to gene flow among C. versicolor populations. Analyses of the data using mismatch distributions and extended Bayesian skyline plots provide evidence of a relatively stable population size through time for Group I, and moderate population expansions and contractions during the end of the Pleistocene for Group II. We conclude that the phylogeographical patterns of C. versicolor are the combined product of Pleistocene sea-level oscillations and nonphysical barriers to gene flow.