There is a consensus that modern humans arrived in the Americas 15,000-20,000 y ago during the Late Pleistocene, most probably from northeast Asia through Beringia. However, there is still debate about the time of entry and number of migratory waves, including apparent inconsistencies between genetic and morphological data on Paleoamericans. Here we report the identification of mitochondrial sequences belonging to haplogroups characteristic of Polynesians in DNA extracted from ancient skulls of the now extinct Botocudo Indians from Brazil. The identification of these two Polynesian haplogroups was confirmed in independent replications in Brazil and Denmark, ensuring reliability of the data. Parallel analysis of 12 other Botocudo individuals yielded only the well-known Amerindian mtDNA haplogroup C1. Potential scenarios to try to help understand these results are presented and discussed. The findings of this study may be relevant for the understanding of the pre-Columbian and/or post-Columbian peopling of the Americas.