In this report, we analyze the phylogeny of Pycnogonida using the three nuclear and three mitochondrial markers currently sequenced for studying inter- and intrafamilial relationships within Arthropoda: 18S and 28S rRNA genes, Histone H3, cytochrome c oxidase subunit 1 (CO1), 12S and 16S rRNA genes. We identify several problems in previous studies, due to the use of inappropriate sequences (taxonomic misidentification, DNA contamination, sequencing errors, missing data) or taxa (outgroup choice). Our analyses show that most markers are not powerful to study the phylogeny of sea spiders. The results suggest however a recent diversification of the group (Mesozoic rather than Paleozoic) and the early divergence of Austrodecidae, followed by Colossendeidae, Pycnogonidae and Rhynchothoracidae. Except Ammotheidae and Callipallenidae, all other families were recovered as monophyletic. Analyses of synonymous sites in CO1 sequences reveal an extreme heterogeneity of nucleotide composition within sea spiders, as six unrelated species show a reverse strand-specific bias. We therefore suggest that several independent reversals of asymmetric mutational constraints occurred during the evolution of Pycnogonida, as a consequence of genomic inversions involving either the control region or a fragment containing the CO1 gene. These hypotheses are supported by the comparison of two complete mitochondrial genomes of sea spiders (Achelia bituberculata and Nymphon gracile) with that of Limulus.