Anopheles dirus and Anopheles baimaii are closely related species which feed on primates, particularly humans, and transmit malaria in the tropical forests of mainland Southeast Asia. Here, we report an in-depth phylogeographic picture based on 269 individuals from 21 populations from mainland Southeast Asia. Analysis of 1537 bp of mtDNA sequence revealed that the population history of A. baimaii is far more complex than previously thought. An old expansion (pre-300 kyr BP) was inferred in northern India/Bangladesh with a wave of south-eastwards expansion arriving at the Thai border (ca 135-173 kyr BP) followed by leptokurtic dispersal very recently (ca 16 kyr BP) into peninsular Thailand. The long and complex population history of these anthropophilic species suggests their expansions are not in response to the relatively recent (ca 40 kyr BP) human expansions in mainland Southeast Asia but, rather, fit well with our understanding of Pleistocene climatic change there.