Pneumodesmus

Pneumodesmus newmani is a species of millipede that lived in the Paleozoic era. Its exact age is uncertain. 428 million years ago in the late Silurian was first suggested. A later study suggested the early Devonian. 
It is the first myriapod fossil, and the oldest known creature to have lived on land. The single specimen was discovered in 2004 near Stonehaven, Aberdeenshire. 
Discovery and naming.
The fossil of "P. newmani" was found by Mike Newman. He is a bus driver and amateur palaeontologist from Aberdeen. The fossil was in a layer of sandstone rocks on the foreshore of Cowie, near Stonehaven. The species was later called "newmani" in honour of its finder. The fossil is kept in National Museum of Scotland, Edinburgh. 
Description.
In the photograph above, you can see the back is covered with hard plates, and wispy slender legs. The animal is definitely segmented, and it is like, or related to, millipedes.
Its cuticle has what look like openings or spiracles. These are part of a gas exchange system that would work in air. So "P. newmani" is thought to be the earliest documented arthropod with a tracheal system, and the first known oxygen-breathing animal on land.