BACKGROUND: Linguistic, cultural and genetic characteristics of the Malagasy suggest that both Africans and Island Southeast Asians were involved in the colonization of Madagascar. Populations from the Indonesian archipelago played an especially important role because linguistic evidence suggests that the Malagasy language branches from the Southeast Barito language family of southern Borneo, Indonesia, with the closest language spoken today by the Ma’anyan. To test for a genetic link between Malagasy and these linguistically related Indonesian populations, we studied the Ma’anyan and other Indonesian ethnic groups (including the sea nomad Bajo) that, from their historical and linguistic contexts, may be modern descendants of the populations that helped enact the settlement of Madagascar. RESULT: A combination of phylogeographic analysis of genetic distances, haplotype comparisons and inference of parental populations by linear optimization, using both maternal and paternal DNA lineages, suggests that Malagasy derive from multiple regional sources in Indonesia, with a focus on eastern Borneo, southern Sulawesi and the Lesser Sunda islands. CONCLUSION: Settlement may have been mediated by ancient sea nomad movements because the linguistically closest population, Ma’anyan, has only subtle genetic connections to Malagasy, whereas genetic links with other sea nomads are more strongly supported. Our data hint at a more complex scenario for the Indonesian settlement of Madagascar than has previously been recognized.