Background/Objectives: In Brazil, quilombos—African-descendant resistance communities—emerged during slavery and persisted beyond its abolition. The state of Paraná, in Southern Brazil, is home to 86 quilombos, yet their genetic diversity remains entirely unexplored, and little is known about their subcontinental African origins. Methods: To explore the demographic history of these communities and the reach of the Transatlantic Slave Trade in Southern Brazil, we analyzed Y and mitochondrial DNA haplotypes in samples from two quilombo communities from Paraná, Feixo (n = 117) and Restinga (n = 47). Results: Our findings reveal a significant African maternal ancestry in both communities, with Feixo exhibiting 35% and Restinga showing a striking 78.72% of maternal haplogroups of African origin. Feixo’s mtDNA haplotypes display affinities with Bantu-speaking populations from Central-Western and Southeastern Africa (such as Angola, Congo, and Mozambique), whereas those found in Restinga are more closely aligned with lineages frequent in Western Africa. Y-chromosome data reveal 39.4% and 25% African paternal ancestry in Feixo and Restinga, respectively, with most African chromosomes assigned to haplogroup E1b1b1-M35, which has a broad frequency across eastern Africa. Conclusions: These results offer novel insights into the history of the African diaspora in a previously unstudied Brazilian region, suggesting African sources—including underdocumented Eastern/Southern lineages—and contributing useful new clues to their broader within-Africa affinities.