We report the first genetic analysis of free-ranging Asian elephants (Elephas maximus). We sampled 118 elephants from Sri Lanka, Bhutan/North India, and Laos/Vietnam by extracting DNA from dung, PCR amplifying and sequencing 630 nucleotides of mitochondrial DNA, including part of the variable left domain of the control region. Comparison with African elephant (Loxodonta africana) sequences indicated a relatively slow molecular clock in the Proboscidea with a sequence divergence of approximately 1%/Myr. Genetic diversity within Asian elephants was low, suggesting a small long-term effective population size. Seventeen haplotypes were identified within Asian elephants, which clustered into two well-differentiated assemblages with an estimated Pliocene divergence of 2.5-3.5 million years ago. The two assemblages showed incomplete geographical partitioning, suggesting allopatric divergence and secondary admixture. On the mainland, little genetic differentiation was observed between elephant populations of Bhutan and India or Laos and Vietnam. A significant difference in haplotype frequencies but relatively weak subdivision was observed between the regions Bhutan-India and Laos-Vietnam. Significant genetic differentiation was observed between the mainland and Sri Lanka, and between northern, mid-latitude and southern regions in Sri Lanka.