The Levant is an important migration bridge, harboring border-zones between Afrotropical and palearctic species. Accordingly, Chameleo chameleon, a common species throughout the Mediterranean basin, is morphologically divided in the southern Levant (Israel) into two subspecies, Chamaeleo chamaeleon recticrista (CCR) and C. c. musae (CCM). CCR mostly inhabits the Mediterranean climate (northern Israel), while CCM inhabits the sands of the north-western Negev Desert (southern Israel). AFLP analysis of 94 geographically well dispersed specimens indicated moderate genetic differentiation (PhiPT = 0.097), consistent with the classical division into the two subspecies, CCR and CCM. In contrast, sequence analysis of a 637 bp coding mitochondrial DNA (mtDNA) fragment revealed two distinct phylogenetic clusters which were not consistent with the morphological division: one mtDNA cluster consisted of CCR specimens collected in regions northern of the Jezreel Valley and another mtDNA cluster harboring specimens pertaining to both the CCR and CCM subspecies but collected southern of the Jezreel Valley. AMOVA indicated clear mtDNA differentiation between specimens collected northern and southern to the Jezreel Valley (PhiPT = 0.79), which was further supported by a very low coalescent-based estimate of effective migration rates. Whole chameleon mtDNA sequencing (∼17,400 bp) generated from 11 well dispersed geographic locations revealed 325 mutations sharply differentiating the two mtDNA clusters, suggesting a long allopatric history further supported by BEAST. This separation correlated temporally with the existence of an at least 1 million year old marine barrier at the Jezreel Valley exactly where the mtDNA clusters meet. We discuss possible involvement of gender-dependent life history differences in maintaining such mtDNA genetic differentiation and suggest that it reflects (ancient) local adaptation to mitochondrial-related traits.