Spanish Ministerio de Economia y Competitividad - Programa CSIC de cooperaci on cient ıfica para el desarrollo (COOP20099), the Agencia Estatal de Investigaci on and Fondo Europeo de Desarollo Regional (FEDER) grant CGL2016-75389-P, the “Unidad de Excelencia Maria de Maeztu” MDM2014-0370, and Secretaria d’Universitats i Recerca del Departament d’Economia i Coneixement de la Generalitat de Catalunya (GRC 2017 SGR 00702). This study was financed in part by the Coordenac¸~ao de Aperfeic¸oamento de Pessoal de N ıvel Superior—Brasil (CAPES)—Finance Code 001. The EPÌGEN Brazil Initiative was funded by the Brazilian Ministry of Health (Department of Science and Technology from the Secretaria de Ci^encia, Tecnologia e Insumos Estrat egicos) through Financiadora de Estudos e Projetos.After the colonization of the Americas by Europeans and the consequent Trans-Atlantic Slave Trade, most Native American populations in eastern Brazil disappeared or went through an admixture process that configured a population composed of three main genetic components: the European, the sub-Saharan African, and the Native American. The study of the Native American genetic history is challenged by the lack of availability of genome-wide samples from Native American populations, the technical difficulties to develop ancient DNA studies, and the low proportions of the Native American component in the admixed Brazilian populations (on average 7%). We analyzed genome-wide data of 5,825 individuals from three locations of eastern Brazil: Salvador (North-East), Bambui (South-East), and Pelotas (South) and we reconstructed populations that emulate the Native American groups that were living in the 16th century around the sampling locations. This genetic reconstruction was performed after local ancestry analysis of the admixed Brazilian populations, through the rearrangement of the Native American haplotypes into reconstructed individuals with full Native American ancestry (51 reconstructed individuals in Salvador, 45 in Bambui, and 197 in Pelotas). We compared the reconstructed populations with nonadmixed Native American populations from other regions of Brazil through haplotype-based methods. Our results reveal a population structure shaped by the dichotomy of Tupi-/Jê-speaking ancestry related groups. We also show evidence of a decrease of the diversity of nonadmixed Native American groups after the European contact, in contrast with the reconstructed populations, suggesting a reservoir of the Native American genetic diversity within the admixed Brazilian population.