This article examines substratal influences in Palenquero (Colombia). It begins with an explanation of why research on the origins of Palenque and its language has been particularly challenging, and what these challenges mean in terms of how convincing the reigning hypothesis of a sole Kikongo substrate can (or cannot) be. The study then concentrates on relevant external and internal language data, as these are in many ways complementary. Language-internal features tied to Kikongo will be shown to come from all domains of grammar (phonology, morphology and syntax). Three fundamental conclusions will be reached: (1) Kikongo speakers must indeed have been a dominant force in the early Palenque; (2) lacunae in our historical and linguistic knowledge are, however, so great that we should keep a guarded attitude toward the current substrate hypothesis; and (3) there are multiple reasons to be optimistic about future attempts to refine substratist investigations into the creole. Part of that optimism rests on ongoing DNA research (based on comparison of the DNA of Palenqueros and Central West Africans), as well as on an astonishing turnaround of sociolinguistic attitudes in twenty-first-century Palenque. This turnaround has prompted a rapid re-evaluation and never-before seen appreciation of local Africanisms. Local enthusiasm for Palenquero is currently bringing to the fore a corpus of hitherto undocumented ancestral words that may help us advance explorations into the origins of the language.