ABSTRACT: BACKGROUND: The phylogeny of Arthropoda is still a matter of harsh debate among systematists, and significant disagreement exists between morphological and molecular studies. In particular, while the taxon joining hexapods and crustaceans (the Pancrustacea) is now widely accepted among zoologists, the relationships among its basal lineages, and particularly the supposed reciprocal paraphyly of Crustacea and Hexapoda, continues to represent a challenge. Several genes, as well as different molecular markers, have been used to tackle this problem in molecular phylogenetic studies, with the mitochondrial DNA being one of the molecules of choice. In this study, we have assembled the largest data set available so far for Pancrustacea, consisting of 100 complete (or almost complete) sequences of mitochondrial genomes. After removal of unalignable sequence regions and highly rearranged genomes, we used nucleotide and inferred amino acid sequences of the 13 protein coding genes to reconstruct the phylogenetic relationships among major lineages of Pancrustacea. The analysis was performed with Bayesian inference, and for the amino acid sequences a new, Pancrustacea-specific, matrix of amino acid replacement was developed and used in this study. RESULTS: Two largely congruent trees were obtained from the analysis of nucleotide and amino acid datasets. In particular, the best tree obtained based on the new matrix of amino acid replacement (MtPan) was preferred over those obtained using previously available matrices (MtArt and MtRev) because of its higher likelihood score. The most remarkable result is the reciprocal paraphyly of Hexapoda and Crustacea, with some lineages of crustaceans (namely the Malacostraca, Cephalocarida and, possibly, the Branchiopoda) being more closely related to the Insecta s.s. (Ectognatha) than two orders of basal hexapods, Collembola and Diplura. Our results confirm that the mitochondrial genome, unlike analyses based on morphological data or nuclear genes, consistently supports the non monophyly of Hexapoda. CONCLUSION: The finding of the reciprocal paraphyly of Hexapoda and Crustacea suggests an evolutionary scenario in which the acquisition of the hexapod condition may have occurred several times independently in lineages descending from different crustacean-like ancestors, possibly as a consequence of the process of terrestrialization. If this hypothesis was confirmed, we should therefore re-think our interpretation of the evolution of the Arthropoda, where terrestrialization may have led to the acquisition of similar anatomical features by convergence. At the same time, the disagreement between reconstructions based on morphological, nuclear and mitochondrial data sets seems to remain, despite the use of larger data sets and more powerful analytical methods.