Two fragments of lower jawbone, unearthed from 370-million-year-old rocks in Latvia and Estonia, have features in-between those of fish and land animals.
"Of all the bones in a skeleton that we could have found, the jaw is exactly the right piece, because it carries the signature of the creature," said Dr Per Ahlberg of the Natural History Museum in London, who led the team.
"The jaws of fish and land animals are very different and change dramatically during the evolution process."
Fish ancestors
It has long been accepted that all land animals with backbones - including humans - are descended from one small group of fish that left the water about 365 million years ago.
The emergence of the first backboned land animals, or tetrapods, was not only a key step in our own ancestry, but an event which changed the ecosystem of the land forever. Today, there are at least 25,000 species of tetrapod.
The earliest land animals were fish-like amphibians but until now there was a big gap in the fossil record between the most evolved fish and the earliest amphibians.
These new fossils not only shed light on how fish evolved but also prompt a rethink of where existing fossils fit into the evolutionary jigsaw puzzle.
Legs or fins?
"The question we can't yet answer is whether this creature had paired fins or legs," Dr Ahlberg told BBC News Online.
This find will prompt researchers to start digging through rocks in Eastern Europe to find a complete example of the new creature's skeleton.
"A whole fossilised skeleton of one of these animals would be one of the great discoveries of the century," said Dr Ahlberg.
The name of the new creature is to remain secret until a paper on the discovery is published in the journal Palaeontology in August.
Peculiar teeth
Dr Jenny Clack, of the University Museum of Zoology in Cambridge, said: "The discovery is interesting because it shows a most peculiar tooth arrangement, unlike any other creature in this lineage or elsewhere, to my knowledge."
"The inference is that it had some specialised feeding strategy that we do not understand and that was unusual among this group of beasts."
She added: "In recent years, all sorts of new specimens are coming to light that slot into this part of the family tree, and I suspect we are going to find a lot more in the future. Each one will add a bit more detail."