San Basilio de Palenque is an Afro-descendant community near Cartagena, Colombia, founded in the sixteenth century. The recognition of the historical and cultural importance of Palenque has promoted several studies, namely concerning the African roots of its first inhabitants. To deepen the knowledge of the origin and diversity of the Palenque parental lineages, we analysed a sample of 81 individuals for the entire mtDNA Control Region as well as 92 individuals for 27 Y-STRs and 95 for 51 Y-SNPs. The results confirmed the strong isolation of the Palenque, with some degree of influx of Native American maternal lineages, and a European admixture exclusively mediated by men. Due to the high genetic drift observed, a pairwise FST analysis with available data on African populations proved to be inadequate for determining population affinities. In contrast, when a phylogenetic approach was used, it was possible to infer the phylogeographic origin of some lineages in Palenque. Contradicting previous studies indicating a single African origin, our results evidence parental genetic contributions from widely different African regions.