While no fossilized bones have been found from these enigmatic people, they did leave their mark in present-day Africans: snippets of foreign DNA.
Scientists insist that there's only one way that genetic material could have made it into modern human populations.
"Geneticists like euphemisms, but we're talking about sex," the Washington Post quoted Joshua Akey of the University of Washington in Seattle, whose lab identified the mystery DNA in three groups of modern Africans, as saying.
According to Akey, these genetic leftovers do not resemble DNA from any modern-day humans. The foreign DNA also does not resemble Neanderthal DNA, which shows up in the DNA of some modern-day Europeans.
That means the newly identified DNA came from an unknown group.
"We're calling this a Neanderthal sibling species in Africa," Akey said.
He further said that the interbreeding probably occurred 20,000 to 50,000 years ago, long after some modern humans had walked out of Africa to colonize Asia and Europe, and around the same time Neanderthals were declining in Europe.
The find offers more evidence that for thousands of years, modern-looking humans shared the Earth with evolutionary cousins that later became extinct.
And whenever the groups met, whether in Africa or Europe, they bred.
In fact, hominid hanky-panky seems to have occurred wherever humans met others who looked kind of like them - a controversial idea until recently.
The research was recently published in the journal Cell:
Evolutionary History and Adaptation from High-Coverage Whole-Genome Sequences of Diverse African Hunter-Gatherers, Cell, Volume 150, Issue 3, 457-469, 26 July 2012