The effects of Pleistocene environmental fluctuations on the distribution and diversity of organisms in Southeast Asia are much less well known than in Europe and North America. In these regions, the combination of palaeoenvironmental reconstruction and inferences about population history from genetic data has been very powerful. In Southeast Asia, mosquitoes are good candidates for the genetic approach, with the added benefit that understanding the relative contributions of historical and current processes to population structure can inform management of vector species. Genetic variation among populations of Anopheles minimus was examined using 144 mtDNA COII sequences from 23 sites in China, Thailand and Vietnam. Haplotype diversity was high, with two distinct lineages that have a sequence divergence of over 2% and exhibit different geographical distributions. We compare alternative hypotheses concerning the origin of this pattern. The observed data deviate from the expectations based on a single-panmictic population with or without growth, or a stable but spatially structured population. However, they can be readily accommodated by a model of past fragmentation into eastern and western refugia, followed by growth and range expansion. This is consistent with the palaeoenvironmental reconstructions currently available for the region.