Sambaqui (shellmound) societies are among the most intriguing archaeological phenomena in pre-colonial South America, extending from approximately 8,000 to 1,000 years before present (yr bp) across 3,000 km on the Atlantic coast. However, little is known about their connection to early Holocene hunter-gatherers, how this may have contributed to different historical pathways and the processes through which late Holocene ceramists came to rule the coast shortly before European contact. To contribute to our understanding of the population history of indigenous societies on the eastern coast of South America, we produced genome-wide data from 34 ancient individuals as early as 10,000 yr bp from four different regions in Brazil. Early Holocene hunter-gatherers were found to lack shared genetic drift among themselves and with later populations from eastern South America, suggesting that they derived from a common radiation and did not contribute substantially to later coastal groups. Our analyses show genetic heterogeneity among contemporaneous Sambaqui groups from the southeastern and southern Brazilian coast, contrary to the similarity expressed in the archaeological record. The complex history of intercultural contact between inland horticulturists and coastal populations becomes genetically evident during the final horizon of Sambaqui societies, from around 2,200 yr bp, corroborating evidence of cultural change.