Millipedes of the family Xystodesmidae (Polydesmida) are often host to several symbiotic mite species, but very little work has been done to identify these acarines or to understand their relationship to the millipedes. In an attempt to better understand these associations, mites found on xystodesmid millipedes, a group for which a species phylogeny has been proposed, were collected in the Appalachian Mountains of Kentucky, Virginia, Tennessee and North Carolina. Mites in the genera Stylochyrus Canestrini & Canestrini, 1882 (Mesostigmata: Ologamasidae) and Schwiebea Oudemans, 1916 (Sarcoptiformes: Acaridae) were prevalent among millipedes in the genera Apheloria Chamberlin, 1921, Appalachioria Marek & Bond, 2006, Boraria Chamberlin, 1943, Brachoria Chamberlin, 1939, Dixioria Chamberlin, 1947, Nannaria Chamberlin, 1918, Pleuroloma Rafinesque, 1820, Prionogonus Shelley, 1982, Rudiloria Causey, 1955 and Sigmoria Chamberlin, 1939. Of the mite taxa collected, the species Stylochyrus rarior (Berlese, 1916) was found on the greatest number of sampled millipede taxa. To enhance future coevolutionary studies of xystodesmid millipedes and their mite symbionts, the complete mitochondrial genome of S. rarior associated with the millipede genus Apheloria (Polydesmida: Xystodesmidae) was sequenced. The genome is 14 899 nucleotides in length, has all the typical genes of an arthropod mitochondrion, differs in gene arrangement from that of the ancestral arthropod, and has a gene order that is unique among mites and ticks. The major difference in S. rarior is the placement of the protein-coding gene nad1, which is positioned between the rRNA gene 12S and the protein-coding gene nad2 (tRNA genes and non-coding regions excluded). There are also two non-coding control regions within this mitochondrial genome.