Due to habitat fragmentation and conflicts with humans, distribution and abundance of Asian elephant have declined throughout mainland Southeast Asia (Indochina), however the impacts of this fragmentation on the genetic diversity and connectivity of important regional populations is unknown. First, we assessed the demographic history of Indochinese elephants using 600-bp mtDNA sequences to test the prediction of long-term stability of this population dating back 600 KYA. Second, in the current timeframe, we used 10 microsatellite loci from 167 dung samples to test whether there were genetic structures between the Western Forest Complex (WEFCOM) and Kaeng Krachan Forest Complex (KKFC), two large protected areas which were formerly connected as part of the Tenasserim Range along the Thailand-Myanmar border. From 39 mtDNA variable sites, we identified 13 haplotypes: 6 α and 7 β haplotypes. The presence of two highly divergent clades splitting approximately 2.149 MYA suggests the Tenasserim is a zone of secondary contact of individuals previously isolated in at least two refugia. Four α and 1 β haplotypes were unique to the Tenasserim. A Bayesian skyline plot of the a haplotypes indicated a large, stable effective size of females (Nef =13,000) in Indochina since 600 KYA. However, the estimated low current gene flow (within five generations or 100 years) across landscape was insufficient to prevent genetic differentiation (RST=0.03, K=2) between WEFCOM and KKFC based on our spatially explicit model. Landscape planning that restores dispersal between these populations is needed to ensure viability of elephant populations in the Tenasserim landscape.