Hainan, an island linking mainland East Asia and Southeast Asia, lay in one of the routes of early migration to East Asia. The largest indigenous group of Hainan is called Hlai, possibly direct descendants of the earliest migrants. However, there are no sufficient genetic data to assess the population history of Hainan Island. Here, we have analyzed mitochondrial DNA control-region and coding-region sequence variations in 566 Hlai individuals from all five subgroups, Ha, Gei, Zwn, Moifau, and Jiamao. Our results suggest three phases for the peopling of Hainan. The first phase represents the initial settlement of the island as part of the African dispersal approximately 50 000 years ago. The second phase reflects colonization events from mainland Asia before the Last Glacial Maximum, which was recorded by wide distributed lineages, such as F*, B4a, and D4a.The third phase reflects population expansions under lineages F1b, M7b, and R9b after the Last Glacial Maximum and Neolithic migrations in and out of Hainan Island. Selection also started to play a role during the last phase. We also detected different distributions between paternal Y chromosome and maternal mitochondrial DNA among isolated Hlai populations, which might be caused by sex-biased cultural practices.