The discovery was made by amateur fossil hunter Mike Newman.

It is thought that the one-centimetre millipede which was prised out of a siltstone bed is 428 million years old.

Experts at the National Museums of Scotland and Yale University, US, have studied the fossil for months.

They say the specimen is the earliest evidence of a creature living on dry land, rather than in the sea.

The discovery on the foreshore of Cowie Harbour was made by an amateur fossil hunter, Mike Newman.

To recognise his role in the significant find, the new species - Pneumodesmus newmani - has been named after him.

Scotland has the best Palaeozoic, pre-Triassic, pre-dinosaur sites in the world Mike Newman Fossil hunter

The Aberdeen bus driver, who lives in Kemnay, told the Sunday Herald newspaper: "I knew that the site had been re-aged, that it was older than originally thought, so I went down there.

"I knew that any terrestrial-type things with legs found there could be early and important.

"I had found millipedes there before, but this one had evidence of the holes that showed it actually breathed.

"I'm interested in particular in fossil fish; I describe the fish in scientific journals, but things like this creature I pass on."

He added: "Scotland has the best Palaeozoic - pre-Triassic, pre-dinosaur - sites in the world.

The fossil is thought to be 428 million years old

"There are more sites in the small country of Scotland than the whole of the US and Russia put together.

"It's a fantastic place for these very old invertebrates. Just think, the first air-breathing creature crawled out of the swamp at Stonehaven."

The fossil is believed to be some 20 million years older than what had previously been thought of as the oldest breathing animal - a peculiar spider-like creature in Aberdeenshire.

The millipede had spiracles, or primitive breathing structures on the outside of its body, making it the oldest air-breathing creature to have been discovered.