The subphylum Myriapoda included four extant classes (Chilopoda, Symphyla, Diplopoda and Pauropoda), but very little work has been done to explore their phylogenetic relationships. Herein, we determined the complete mitochondrial genome of Polydesmus sp. GZCS-2019 (Myriapoda: Polydesmida) and the mitochondrial genomes are circular molecules of 15,036 bp, with all genes encoded on + strand. The A+T content is 66.1%, making the chain asymmetric, and exhibits negative AT-skew (-0.236). Several genes rearrangements were detected and we propose a new rearrangement model: “TD (N\R) L + C” based on the genome-scale duplication + (non-random/random) loss + recombination. Phylogenetic analyses demonstrated that Chilopoda and Symphyla both were monophyletic group, whereas Pauropoda was embedded in Diplopoda to form the Dignatha. Divergence time showed the first split of Myriapoda occurred between the Chilopoda and other classes (Wenlock period of Silurian). We combine phylogenetic analysis, divergence time, and gene arrangement to yield valuable insights into the evolutionary history and classification relationship of Myriapoda and these results support a monophyletic Progoneata and the relationship (Chilopoda + (Symphyla + (Diplopoda + Pauropoda))) within Myriapod. Our results help to better explain the gene rearrangement events of the invertebrate mitogenome and lay the foundation for further phylogenetic study of Myriapoda.