Proof of the creatures' existence, which lived 260million years ago, has been found in Torbay, Devon.
The worms, which grew up to 3ft long and 6in wide, are thought to have lived underground before dinosaurs roamed the earth.
Experts at the English Riviera Geopark organisation have found large burrow holes that are said to have been made by the creatures as they travelled beneath the surface.
Geologist Dr Kevin Page said the discovery of the underground holes is an unprecedented find in science and represents "life - but not as we know it".
He said: "It really is quite extraordinary. Nothing like this has ever been found before. The underground area is peppered with these burrows.
"There is no supporting evidence to suggest they were made by creatures we know about, so what were are looking at is an entirely new life form.
"It is very, very strange. They were made at the end of the Paleozoic period before dinosaurs came along when the earth teemed with creatures which are now extinct.
"We have found the holes but as yet we haven't found the animals which made them.
"They would have looked like the worms from the film Dune. It is science fiction meeting science fact.
"We know about giant millipedes at the time but this is something quite different. They are unknown to science and a completely new species. It is life, but not as we know it."
The large holes were found across an area of sediment at the bottom of what was a desert wadis (corr) - a valley or dry river bed that only contains water during times of heavy rain.
Dr Page, a lecturer at Plymouth University, said the worms lived underground and only come to the surface to drink and feed.