No fossil evidence of the previously unknown humans exists, researchers said, but they left their mark in bits of foreign DNA in modern-day African populations.
The existence of that genetic material in modern human populations is proof of interbreeding between the two species, probably 20,000 to 50,000 years ago, they said.
"Geneticists like euphemisms, but we're talking about sex," Joshua Akey of the University of Washington in Seattle told The Washington Post.
Akey's lab identified the mystery DNA in three groups of modern Africans.
"We're calling this a Neanderthal sibling species in Africa," Akey said.
The time of the interbreeding would have been long after some modern humans had walked out of Africa to colonize Asia and Europe, he said, and around the same time Neanderthals were on the decline in Europe.
Present-day Europeans show no evidence of the foreign DNA, suggesting the mystery people were likely confined to Africa, he said.
While modern humans and the newly found "archaic" Africans might be classified as distinct species, they managed to produce viable offspring, Akey said.
"They had to be similar enough in appearance to anatomically modern humans that reproduction would happen," Akey said.
However, with no fossils in hand, he acknowledged, it's impossible to say what these people looked like.