Myriapoda, a subphylum of Arthropoda, comprises four classes, Chilopoda, Diplopoda, Pauropoda and Symphyla. While recent molecular evidence has shown that Myriapoda is monophyletic, the internal phylogeny, which is pivotal for understanding the evolutionary history of myriapods, remains unresolved. Here we report the results of phylogenetic analyses and estimations of divergence time and ancestral state of myriapods. Phylogenetic analyses were performed based on three nuclear protein-coding genes determined from 19 myriapods representing the four classes (17 orders) and 11 outgroup species. The results revealed that Symphyla whose phylogenetic position has long been debated is the sister lineage to all other myriapods and that the interordinal relationships within classes were consistent with traditional classifications. Ancestral state estimation based on the tree topology suggests that myriapods evolved from an ancestral state that was characterized by a hemianamorphic mode of post-embryonic development and had a relatively low number of body segments and legs.