Onychophora (velvet worms) play a crucial role in current discussions on position of arthropods. The ongoing Articulata/Ecdysozoa debate is in need of additional ground pattern characters for Panarthropoda (Arthropoda, Tardigrada, and Onychophora). Hence, Onychophora is an important outgroup taxon in resolving the relationships among arthropods, irrespective of whether morphological or molecular data are used. To date, there has been a noticeable lack of mitochondrial genome data from onychophorans. Here, we present the first complete mitochondrial genome sequence of an onychophoran, Epiperipatus biolleyi (Peripatidae), which shows several characteristic features. Specifically, the gene order is considerably different from that in other arthropods and other bilaterians. In addition, there is a lack of 9 tRNA genes usually present in bilaterian mitochondrial genomes. All these missing tRNAs have anticodon sequences corresponding to 4-fold degenerate codons, whereas the persisting 13 tRNAs all have anticodons pairing with 2-fold degenerate codons. Sequence-based phylogenetic analysis of the mitochondrial protein-coding genes provides a robust support for a clade consisting of Onychophora, Priapulida, and Arthropoda, which confirms the Ecdysozoa hypothesis. However, resolution of the internal ecdysozoan relationships suffers from a cluster of long-branching taxa (including Nematoda and Platyhelminthes) and a lack of data from Tardigrada and further nemathelminth taxa in addition to nematodes and priapulids.