In this study, mitochondrial sequences were used to investigate the relationships among the major lineages of Arthropoda. The data matrix used for the analyses includes 84 taxa and 3918 nucleotides representing six mitochondrial protein-coding genes (atp6 and 8, cox1-3, and nad2). The analyses of nucleotide composition show that a reverse strand-bias, i.e., characterized by an excess of T relative to A nucleotides and of G relative to C nucleotides, was independently acquired in six different lineages of Arthropoda: (1) the honeybee mite (Varroa), (2) Opisthothelae spiders (Argiope, Habronattus, and Ornithoctonus), (3) scorpions (Euscorpius and Mesobuthus), (4) Hutchinsoniella (Cephalocarid), (5) Tigriopus (Copepod), and (6) whiteflies (Aleurodicus and Trialeurodes). Phylogenetic analyses confirm that these convergences in nucleotide composition can be particularly misleading for tree reconstruction, as unrelated taxa with reverse strand-bias tend to group together in MP, ML, and Bayesian analyses. However, the use of a specific model for minimizing effects of the bias, the "Neutral Transition Exclusion" (NTE) model, allows Bayesian analyses to rediscover most of the higher taxa of Arthropoda. Furthermore, the analyses of branch lengths suggest that three main factors explain accelerated rates of substitution: (1) genomic rearrangements, including duplication of the control region and gene translocation, (2) parasitic lifestyle, and (3) small body size. The comparisons of Bayesian Bootstrap percentages show that the support for many nodes increases when taxa with long branches are excluded from the analyses. It is therefore recommended to select taxa and genes of the mitochondrial genome for inferring phylogenetic relationships among arthropod lineages. The phylogenetic analyses support the existence of a major dichotomy within Arthropoda, separating Pancrustacea and Paradoxopoda. Basal relationships between Pancrustacean lineages are not robust, and the question of Hexapod monophyly or polyphyly cannot be answered with the available mitochondrial sequences. Within Paradoxopoda, Chelicerata and Myriapoda are each found to be monophyletic, and Endeis (Pycnogonida) is, surprisingly, associated with Acari.