The superorder Psocodea has ∼10,000 described species in two orders: Psocoptera (barklice and booklice) and Phthiraptera (parasitic lice). One booklouse, Liposcelis bostrychophila and six species of parasitic lice have been sequenced for complete mitochondrial (mt) genomes; these seven species have the most rearranged mt genomes seen in insects. The mt genome of a barklouse, lepidopsocid sp., has also been sequenced and is much less rearranged than those of the booklouse and the parasitic lice. To further understand mt gene rearrangements in the Psocodea, we sequenced the mt genomes of two barklice, Psococerastis albimaculata and Longivalvus hyalospilus, the first representatives from the suborder Psocomorpha, which is the most species-rich suborder of the Psocodea. We found that these two barklice have the least rearranged mt genomes seen in the Psocodea to date: a protein-coding gene (nad3) and five tRNAs (trnN, trnS1, trnE, trnM and trnC) have translocated. Rearrangements of mt genes in these two barklice can be accounted for by two events of tandem duplication followed by random deletions. Phylogenetic analyses of the mt genome sequences support the view that Psocoptera is paraphyletic whereas Phthiraptera is monophyletic. The booklouse, L. bostrychophila (suborder Troctomorpha) is most closely related to the parasitic lice. The barklice (suborders Trogiomorpha and Psocomorpha) are closely related and form a monophyletic group. We conclude that mt gene rearrangement has been substantially faster in the lineage leading to the booklice and the parasitic lice than in the lineage leading to the barklice. Lifestyle change appears to be associated with the contrasting rates in mt gene rearrangements between the two lineages of the Psocodea.