Abstract This article examines African influences on Palenquero, a creole language spoken in El Palenque de San Basilio (Colombia). The introduction offers an explanation as to why investigations into the (African) origins of Palenque and its creole have presented special challenges. The study then turns to the reigning hypothesis, according to which Kikongo is the sole substrate of Palenquero. Language-internal data (taken from the lexicon, phonology, and morphosyntax) as well as language-external information are examined to show that these are mutually complementary and confirm Kikongo as the dominant (if not sole) African substrate. Three fundamental conclusions will be reached: (1) Kikongo-speakers must indeed have been a dominant force in the early Palenque (ca. 1670–1725); (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 very optimistic about future attempts to refine substratist investigations into the creole. Part of that optimism rests on 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 21st-century Palenque. This turnaround has prompted a rapid re-evaluation and never-before seen appreciation of local Africanisms. At present, this enthusiasm is helping to reveal previously undocumented lexical Africanisms, which may soon shed additional light on Palenqueros’ Subsaharan provenance.