We review issues of myriapod phylogeny, from the position of the Myriapoda amongst arthropods to the relationships of the orders of the classes Chilopoda and Diplopoda. The fossil record of each myriapod class is reviewed, with an emphasis on developments since 1997. We accept as working hypotheses that Myriapoda is monophyletic and belongs in Mandibulata, that the classes of Myriapoda are monophyletic, and that they are related as (Chilopoda (Symphyla (Diplopoda+Pauropoda))). The most pressing challenges to these hypotheses are some molecular and developmental evidence for an alliance between myriapods and chelicerates, and the attraction of symphylans to pauropods in some molecular analyses. While the phylogeny of the orders of Chilopoda appears settled, the relationships within Diplopoda remain unclear at several levels. Chilopoda and Diplopoda have a relatively sparse representation as fossils, and Symphyla and Pauropoda fossils are known only from Tertiary ambers. Fossils are difficult to place in trees based on living forms because many morphological characters are not very likely to be preserved in the fossils; as a consequence, most diplopod fossils have been placed in extinct higher taxa. Nevertheless, important information from diplopod fossils includes the first documented occurrence of air-breathing, and the first evidence for the use of a chemical defense. Stem-group myriapods are unknown, but evidence suggests the group must have arisen in the Early Cambrian, with a major period of cladogenesis in the Late Ordovician and early Silurian. Large terrestrial myriapods were on land at least by mid-Silurian. Copyright (c) 2009 Elsevier Ltd. All rights reserved.