The status of Myriapoda (whether mono-, para- or polyphyletic) and position of myriapods in the Arthropoda are controversial, an impediment to evaluating fossils that may be members of the myriapod stem-group. Parsimony analysis of 319 characters for extant arthropods provides a basis for defending myriapod monophyly and identifying those morphological characters that are necessary to assign a fossil taxon to the Myriapoda. The alliance of hexapods and crustaceans need not relegate myriapods to the arthropod stem-group; the Mandibulata hypothesis accommodates Myriapoda and Tetraconata as sister taxa. No known pre-Silurian fossils have characters that convincingly place them in the Myriapoda or the myriapod stem-group. Because the strongest apomorphies of Myriapoda are details of the mandible and tentorial endoskeleton, exceptional fossil preservation seems necessary to recognise a stem-group myriapod.