Though there are no body fossils of myriapods fround from the Ordovician, ichnofossil burrows have been reported from the Juniata Formation during the late Ordovician from Central Pennsylvania (Retallack and Feakes, 1987; Rettalack, 2001). Within the burrows (of ichnospecies, Scoyenia beerboweri) are hypothesized fossilized egested sediments, much like those in the burrows of present day millipedes.
During the Silurian, the fossil record contains the first known evidence of both centipedes and millipedes. The first myriapod, and the first known terrestrial oxygen-breathing organism was the millipede Pneumodesmus newmani from the mid Silurian, 425mya, late Wenlock to early Ludlow age (Wilson and Anderson, 2004). This fossil displays cuticular openings which taxonomists interpret as spiracles, or atmospheric oxygen intake organs. The first centipede in the fossil record is from macerates, or cuticle remnants from hydrofluoric acid-dissolved rocks, of the Late Silurian, 415mya (Jeram, et al. 1990).
Millipede fossils are common in the early Devonian (e.g., Archidesmus macnicoli, from Forfar Scotland; and Palaeodesmus tuberculata, from Ayrshire, Scotland) (Wilson and Anderson, 2004). Interestingly, millipede fossils are absent from the middle and late Devonian deposits, but are present in abundance later in the Carboniferous.
Some of the largest terrestrial arthropods were millipedes. Based on the trackways of the arthropleuridan genus, Arthropleura, from the Lower Carboniferous, Briggs, et al. (1984) estimated that the creator must have been two meters long and one meter wide.
The Upper Carboniferous fossil Anthracodesmus macconochiei from Lennel Braes, Cold Stream, Scotland, is one of only a few species in the order Euphoberiida. Like most millipedes from the Paleozoic, the disparity is great (most likely due to the high diversity and low preservation potential) therefore many monotypic genera, families, even orders are established (Wilson and Anderson, 2004).
The millipede suborder Arthropleurida is known from the Carboniferous Visean age to the Asselian age of the Permian (Ryan, 1986).