Linguistic and cultural evidence, strongly supported by archaeological evidence, population genetic evidence, evidence of Indonesian plants that appeared in Africa with Austronesian names around that time (e.g. the banana is native to Southeast Asia, not to Africa), and evidence of Austronesian seamanship in Oceania that make such a journey plausible, all combine to make the settlement of Madagascar one of the most well established and remarkable long distance migrations of a whole people in pre-modern human history.
The story from the genetic evidence
A number of studies have been done of the non-recombining Y-DNA population genetics, mtDNA population genetics, and autosomal population genetics of the Malagasy people.. These studies show significant (but differing) relative proportions of Asian and African genetic origins in Y-DNA, mtDNA, and autosomal DNA. Only a small portion of Malagasy individuals are entirely Asian or entirely African as measured by their Y-DNA, mtDNA and autosomal DNA. The vast majority of the Asian genetic contribution to this population is consistent with origins in Southern Borneo. Based on the mtDNA diversity in the Asian part of the mtDNA of the Malagasy people, it is estimated that there were only about thirty women in the Indonesian founding population of the island.
The African component of the population genetic makeup of the Malagasy people is a better match, in Y-DNA, mtDNA and autosomal genetics, to East African Bantus, such as the Luhya people, than to any other modern African population.
The African component of the uniparental and autosomal components of Malagasy population genetics. As a percentage of the total mtDNA mix in the Malagasy population, the African haplogroup breakdown in one study was as follows :
Of these mtDNA haplogroups, all are very typical of Bantu populations except L* (which may in this context mean L not elsewhere classified rather than maximally basal form of haplogroup L).
As a percentage of the total Y-DNA mix in the Malagasy population, the African haplogroup breakdown was comprised mostly of E3a (36% of the total), with smaller amounts of E2b, E1b1a, and B2. These are mostly characteristic Bantu Y-DNA haplogroups.
Genetics blogger Razib Khan compared the whole genomes of two Malagasy individuals to a number of reference populations. He used software that does a best fit of the data from the reference populations and subjects to ten hypothetical source populations using what amounts to eigenvector analysis of the data sets. With this software, he was able to estimate the percentage of the African component in the Malagasy individuals attributable to each of the source populations, and to compare the mix of African autosomal genetic components in these individuals to those in his African reference populations.
The largest African component in each Malagasy individual was a component which makes up about 90% to 95% of the Mandenka and Yoruba populations, which a Bantu peoples from near the Nigeria-Cameroon border where the Bantu people originated. There was also small contributions of from other African autosomal genetic components:
*About 3-4% (of the total) of a component that is modal in the pastoralist Nilo-Saharan Maasi of East Africa and in Ethiopian Jews. This contribution made up about the same share of the African autosomal genetics of both Malagasy individuals, but in each case was smaller relative to the Bantu contribution than in the East African Bantu Luhya reference population.
*About 2-4% (of the total) of the various components that are predominant in Biaka Pygmies, Mbuti Pygmies, the San people, and the Sandawe people of Africa (all of whom are relict hunter-gatherer populations in Africa). The proportion of these components in the Malagasy individuals relative to the size of their Bantu genetic component was very similar to that seen in the East African Bantu Luhya reference population.
*There was no evidence of admixed contributions from Yemen Jews (a SW Asian reference population) or a European reference population, although there were both SE Asian and South Asian autosomal components of the Asian part of their autosomal genetics.
In sum, Razib Khan's detailed, nuts and bolts autosomal genetic analysis of Malagasy individuals shows that the African contribution to their autosomal DNA looks very much like that of East African Bantu Luhya people, except that the East African Bantus show more Nilo-Saharan admixture.
History may explain the discrepancy. It is likely that a group of Africans joined a group of Borneans with some minor South Asian admixture to make the trip to Madagascar and settled there at around this earliest archaeologically supported data for an Indonesian presence in Madagascar around 500 CE. There is historical and prehistory evidence (including Maasai oral histories) to suggest that the Maasai people and other Nilo-Saharan peoples migrated through East Africa from North to South starting around the 1400s CE. If this contact resulted in some level of admixture in the hundred of years between then and the present, we would expect modern East African Bantus to have more Nilo-Saharan admixture today than they did in the 500s CE at the time of the fusional proto-Malay ethnogenesis.
Other autosomal genetic studies of the Malagasy people have likewise concluded that the African component of the Malagasy autosomal gene pool is basically Bantu in character. And, the uniparental genetic studies have similarly been congruent with a predominantly East African Bantu source for the African component of the Malagasy gene pool.
Notably, the only study of which I am aware of the autosomal population genetics of Mozambique, the Southeastern African country closest to the island of Madagascar specifically noted that the Bantu people of Mozambique are not genetically similar to any of the three reference populations that Razib Khan compared to the two Malagasy individuals for whom he had whole genome data: the Mandenka and Yoruba populations, and the East African Bantu Luhya people. The population genetics of the Bantus of Mozambique show far less population replacement and far more assimilation of an indigenous pre-Bantu population that is genetically distant from any of the extant relict hunter-gather "Paleo-African" populations of Africa that are extant today.
The studies of autosomal genetics in Madagascar that have been done to date either showed no sign at all of a Mozambique component to the gene pool of the Malagasy people,, although one uniparental study did see some sign of a trace and secondary contribution of Mozambique or the vicinity. That 2009 high resolution uniparental genetics study stated:
The pattern of diffusion of uniparental lineages was compatible with at least two events: a primary admixture of proto-Malay people with Bantu speakers bearing a western-like pool of haplotypes, followed by a secondary flow of Southeastern Bantu speakers unpaired for gender (mainly male driven) and geography (mainly coastal).Thus, a small number of Malagasy people have Y-DNA haplotypes associated with coastal Mozambique or the vicinity, and an even smaller number of individuals have mtDNA haplogroups that are distinctively from there.
The new evidence
A study released this summer complicates this neat and simple narrative.
The new study finds clearly modern human microlithic stone tools and other artifacts in layers of two long occupied terrestrial forager villages in Madagascar dating back to about 2000 BCE, about 2500 years before the earliest solid evidence of proto-Malagasy settlement in Madagascar. These settlements also greatly predate the megafauna extinctions that occurred in Madagascar when the mix of Borneans and East African Bantus who gave rise to the Malagasy people arrived.
This first wave of settlers must have been either entirely replaced or swamped demographically by the proto-Malay people who arrived around 500 CE. The people who were in the first wave of human settlers of Madagascar could not have been Bantus, because the Bantu expansion, which began about 2000 BCE in West Africa near the Nigeria-Cameroon border, did not reach the East African coast until ca. 1000 BCE. But, the African genetic component of the Malagasy people is East African Bantu which is very different from that of all coastal populations of Africa around 2000 BCE, so this genetic contribution to the Malagasy people must have arrived later, probably in the same boats that the Austronesians did. The absence of non-Eastern Bantu genes in the Malagasy gene pool, establishes that these indigenous foragers of Madagascar did not contribute much to the modern gene pool, either because they were entirely replaced, or because their contribution was so small in proportion to the newcomers that it has left almost no discernible mark on the modern gene pool in Madagascar.
Alternatively, the foragers could have been relocated to continental Africa by the Austronesians, in a manner similar to the relocation of Native Americans to reservations in early American history, although this seems like a possibility with fewer historical precedents in the expansion histories of the Austronesian and Bantu peoples who made up the proto-Malays.
The data interpreted as a subsequent and secondary wave of male dominated migration from Mozambique in the high resolution uniparental genetic data  could really be, at least in part, a relict of pre-Malay African foragers in Madagascar. But, the fact that the Southeast African uniparental genetic haplogroups are male dominated disfavors a relict population as the primary source of these Southeast African uniparental genetic haplogroups in the Malagasy gene pool. Generally, when an indigenous substrate population is demographically swamped by a newly arrived dominant superstrate population, more matriline transmitted mtDNA survives in the resulting gene pool from the substate population than Y-DNA.
So, the maximum contribution of a relict population to the Malagasy gene pool is probably some fraction of the distinctively Southeast African contribution that was observed in  and the data are not inconsistent with a total replacement of the first wave humans of Madagascar by the proto-Malays that left no surviving genetic trace of this first wave forager population (i.e. with genocide).
Why didn't first wave human settlers of Madagascar cause a mega-fauna extinction?
Equally important, why didn't the arrival of African foragers ca. 2000 BCE result in a mega-fauna extinction in Madagascar as hunter-gatherer migrations into Australia and Papua New Guinea, into the Americas, in Europe and into Siberia did tens of thousands of years earlier with presumably more primitive technology?
This is also not a case comparable to that of continental Africa where the local wildlife co-evolved with modern humans and their hominin predecessors and hence learned to survive in spite of them for tens of thousands of years.
How could this be possible?
Here is one speculative narrative that could explain this new discovery.
The arrival of this first wave of African foragers may have been a one way trip by a small population made possible only by luck and pluck that wasn't repeated. If these foragers had been able to reliably navigate to Madagascar and back at the time, presumably, they would have engaged in trade with mainland Africa. But, there is no archaeological evidence of ongoing trade between Madagascar and continental African prior to 500 CE, which would have been highly distinctive in the archaeological record because it contained species of flora and fauna found nowhere in mainland Africa.
In a case similar to that of the people of Tasmania, once separated from their continental African communities, they may have regressed technologically (e.g. in terms of hunting effectiveness) as their population fell below critical mass to sustain this knowledge, if not immediately, after some mishap or bad foraging season or disease outbreak at a latter time. They may have held on to enough cultural capital to be a sustainable population, but may not have been a large enough community to sustain the level of excellence in hunting and gathering practices that made them a dominant species in Africa and Eurasia and the Americas.
Since Madagascar's flora and fauna are so distinct from those of continental Africa, it may also have been the case in which the knowledge the first wave African foragers brought with them from continental Africa may have been of limited usefulness in this new ecology. Since they were not farmers or herders, they would have brought no familiar plants or animals to feed themselves with them. The need to rapidly develop new gathering skill sets could have given this first wave of modern humans on the island a rocky start, causing their population to fall before eventually recovering as they learned to adapt to local conditions. This could have caused them to regress culturally, in part from their loss of important hunting and gathering knowledge. Without the cultural capital shared by other Upper Paleolithic peoples who brought about mega-fauna extinctions (and contributed to the demise of the Neanderthals), they may have lost the capacity to become so dominant as hunters and gatherers who could cause mega-fauna extinctions.
There also isn't even any sign that they brought domesticated dogs with them. Dogs were first domesticated around 30,000 years ago and were widespread by ca. 2000 BCE, even into Australia where they weren't initially present for tens of thousands of years but appeared about 4000 years ago. Perhaps the relevance of domesticated dogs that modern humans brought with them has been underestimated, which could also explain why Southeast Asia, which is a point of origin of many species of domestic dogs, has so less mega-fauna extinction since Southeast Asian fauna co-evolved with these dogs.
Even if the first wave of humans in Madagascar eventually recovered technologically and cultural, centuries later, their recovery may have been gradual enough to be less disruptive to the local ecology.
These disadvantages wouldn't burden later proto-Malays who brought food sources with them, had reliable sea transportation that permitted them to colonize Madagascar at populations in excess of the critical mass needed to sustain their population, and thus didn't need detailed knowledge of how to turn indigenous plants and animals into food and didn't suffer the cultural regression that may have been experienced by first wave foragers on the island twenty-five centuries earlier.
1. Robert E. Deward et al., "Stone tools and foraging in northern Madagascar challenge Holocene extinction models.", PNAS (2013).[doi:10.1073/pnas.1306100110] (Mr. Deward died on April 8, 2013.)
2. Regueiro, et al., "Austronesian genetic signature in East African Madagascar and Polynesia.", Journal of Human Genetics (2008) 53, 106–120; doi:10.1007/s10038-007-0224-4
3. Poetsch, et al., "Determination of population origin: a comparison of autosomal SNPs, Y-chromosomal and mtDNA haplogroups using a Malagasy population as example.", European Journal of Human Genetics (24 April 2013) doi:10.1038/ejhg.2013.51
4. Hurles, et al. "The dual origin of the malagasy in island southeast Asia and East Africa: evidence from maternal and paternal lineages.", Am J Hum Genet. 2005;76;894-901. PMID: 15793703
5. Tofanelli, et al., "On the origins and admixture of Malagasy: new evidence from high-resolution analyses of paternal and maternal lineages.", Mol. Biol. Evol. 26, 2109–2124 (2009) (doi:10.1093/molbev/msp120)
6. Cox, et al., "A small cohort of Island Southeast Asian women founded Madagascar", Proc. R. Soc. B. (21 March 2012) doi: 10.1098/rspb.2012.0012
7. Razib Khan, "The Betsileo of Madagascar are Malay and Bantu.", Gene Expression (October 23, 2011). (Supplemental materials: here).
8. Razib Khan, "The Merina of Madagascar are Malay and Bantu.", Gene Expression (September 9, 2011).
9. Sikora, et al., "A genomic analysis identifies a novel component in the genetic structure of sub-Saharan African populations.", European Journal of Human Genetics (2011) 19, 84–88; doi:10.1038/ejhg.2010.141.
10. Wikipedia entry on "Bantu Expansion" (the Bantu reach the East African coast sometime after 1500 BCE and before 500 BCE; and there is no evidence of Bantu seafaring activity independent of assistance from other cultures such as the Austronesians).
11. Gemma Berniell-Lee, et al., "Genetic and demographic implications of the Bantu expansion: insights from human paternal lineages.", Molecular Biology and Evolution (April 2009) doi:10.1093/molbev/msp069 (quoted at Dienekes' Anthropology Blog)("these lineages have been associated either to Bantu-speaking people - E1b1a (E3a according to The Y Chromosome Consortium (2002)), B2a, and E2 - or to Pygmy populations (haplogroup B2b).").
12. Salas, et al., "The Making of the African mtDNA Landscape", Am J Hum Genet. 71(5): 1082–1111.(November 2002) PMCID: PMC385086. ("L2b, L2c, and L2d appear to be largely confined to West and western Central Africa (and African Americans), with only minor occurrences of a few derived types in the southeast. . . . [L3b is a] major southeastern haplogroups of clear West African origin. . . . L3e1 is distributed throughout sub-Saharan Africa, but it is especially common in southeastern Africa. This clade appears to have a west Central African origin and is rare among West Africans, although it is well represented among African Americans. Several southeastern African types are shared with East African Bantu-speaking Kikuyu from Kenya. This suggests that L3e1 may have spread into Kenya via the eastern stream from a Cameroon source population (best represented in this data set by Bioko and São Tomé) or from some Central African source. It subsequently dispersed into the southeast (although, with so little data, back migration into Kenya cannot be ruled out). The African American types may be the result of direct transportation from Mozambique, given the lack of West African representatives. One L3e1a type is also present at elevated frequency in the Khwe, but, since it matches two Herero and also has a direct derivative in the southeast, this again appears to have been the result of gene flow from Bantu speakers, even though the type has not been sampled in that group.")