The Dicyemida and Orthonectida are two groups of tiny, simple, vermiform parasites that have historically been united in a group named the Mesozoa. Both Dicyemida and Orthonectida have just two cell layers and appear to lack any defined tissues. They were initially thought to be evolutionary intermediates between protozoans and metazoans but more recent analyses indicate that they are protostomian metazoans that have undergone secondary simplification from a complex ancestor. Here we describe the first almost complete mitochondrial genome sequence from an orthonectid, Intoshia linei, and describe nine and eight mitochondrial protein-coding genes from Dicyema sp. and Dicyema japonicum, respectively. The 14 247 base pair long I. linei sequence has typical metazoan gene content, but is exceptionally AT-rich, and has a unique gene order. The data we have analysed from the Dicyemida provide very limited support for the suggestion that dicyemid mitochondrial genes are found on discrete mini-circles, as opposed to the large circular mitochondrial genomes that are typical of the Metazoa. The cox1 gene from dicyemid species has a series of conserved, in-frame deletions that is unique to this lineage. Using cox1 genes from across the genus Dicyema, we report the first internal phylogeny of this group.