Eastern Indonesia possesses more linguistic diversity than any other region in Southeast Asia, with both Austronesian (AN) languages that are of East Asian origin, as well as non-Austronesian (NAN) languages of likely Melanesian origin. Here, we investigated the genetic history of human populations from seven eastern Indonesian islands, including AN and NAN speakers, as well as the relationship between languages and genes, by means of nonrecombining Y-chromosomal (NRY) and mitochondrial DNA (mtDNA) analysis. We found that the eastern Indonesian gene pool consists of East Asian as well as Melanesian components, as might be expected based on linguistic evidence, but also harbors putative indigenous eastern Indonesian signatures that perhaps reflect the initial occupation of the Wallacea by aboriginal hunter-gatherers already in Palaeolithic times. Furthermore, both NRY and mtDNA data showed a complete lack of correlation between linguistic and genetic relationships, most likely reflecting genetic admixture and/or language shift. In addition, we noted a small fraction of the NRY and mtDNA data shared between eastern Indonesians and Australian Aborigines likely reflecting an ancient link between Asia and Australia. Our data thus provide insights into the complex genetic ancestry history of eastern Indonesian islanders characterized by several admixture episodes and demonstrate a clear example of the lack of the often-assumed correlation between the genes and languages of human populations.