Nine fossilised teeth found in Ethiopia are from a previously unknown species of great ape, Nature journal reports.
The teeth have gorilla-like characteristics, say researchers
The 10 million-year-old fossils belong to an animal that has been named Chororapithecus abyssinicus by an Ethiopian-Japanese team.
This new species could be a direct ancestor of living African great apes, say the researchers.
The finds from the Afar rift, in eastern Ethiopia, raise questions on current theories of human evolution.
The researchers say the fossils from Ethiopia probably belonged to an ape from the gorilla family.
Based on genetic evidence, gorillas and humans were thought to have split away from a common ancestor about eight million years ago.
The 10-million-year age of the fossils led the research team to suggest that the split must have happened earlier than 10.5 million years ago.
If correct, molecular and DNA studies will need to be revisited.
The team's claims that the teeth belong to a member of the gorilla family stem from similarities with teeth of modern gorillas.
The fossils were found at a site in eastern Ethiopia's Afar rift
They carried out cutting-edge 3D analysis of the molar tooth's structure and found that both gorillas and the new species had a unique specialisation for eating fibrous foodstuffs such as stems and leaves.
"It's a subtle distinction, but we've compared it with everything we could think of," said Dr Suwa from the University of Tokyo and a member of the research team.
"And it does show some telling signs of gorilla-like molar structure. If it's not a gorilla relative, then it's something very similar to what an early gorilla must have looked like."
Gorillas are unique among modern and fossil large-bodied apes in having molars that are specialised for shredding fibrous vegetation. The reason for this is that large-bodied gorillas depend on stems and leaves as an important part of their diet.
Not everyone agrees with the team's conclusions, however. Professor Peter Andrews, from London's Natural History Museum, commented: "It is stretching the evidence to base a time scale for the evolution of the great apes on this new fossil."
Professor Andrews believes the structures found on the teeth could be related to the diet of the animal.
He added: "These structures appear on at least three independent lineages of apes, including gorillas, and they could relate to a dietary shift rather than indicating a new genetic trait."
What is not in doubt is that the find itself is impressive.
"The ancestry of humans is increasingly well known, but the fossil evidence for the evolution of our closest living relatives, the great apes, is almost non-existent," Professor Andrews explained.
"It is really exciting therefore to find a fossil ape from this time period - about 10 million years ago - since there is only one other fossil ape known from this time, the more complete Samburupithecus."
The find also supports data that suggests Africa was the origin of both humans and modern African apes.
The teeth were discovered in a region that is about 170km (110 miles) east of Addis Ababa.
In an area of the Oromiya National Regional State, there are exposed patches of sediments that are 10 to 11 million years old, putting them in the Miocene Epoch. Hence, they are known as Miocene Chorora Formation.
The name of the ape is taken from the geological formation Chorora and the former name of Ethiopia, Abyssinia.