Bryozoans are aquatic colonial suspension-feeders abundant in many marine and freshwater benthic communities. At the same time, the phylum is under studied on both morphological and molecular levels, and its position on the metazoan tree of life is still disputed. Bryozoa include the exclusively marine Stenolaemata, predominantly marine Gymnolaemata and exclusively freshwater Phylactolaemata. Here we report the mitochondrial genome of the phylactolaemate bryozoan Cristatella mucedo. This species has the largest (21,008 bp) of all currently known bryozoan mitogenomes, containing a typical metazoan gene compendium as well as a number of non-coding regions, three of which are longer than 1500 bp. The trnS1/trnG/nad3 region is presumably duplicated in this species. Comparative analysis of the gene order in C. mucedo and another phylactolaemate bryozoan, Pectinatella magnifica, confirmed their close relationships, and revealed a stronger similarity to mitogenomes of phoronids and other lophotrochozoan species than to marine bryozoans, indicating the ancestral nature of their gene arrangement. We suggest that the ancestral gene order underwent substantial changes in different bryozoan clades showing mosaic distribution of conservative gene blocks regardless of their phylogenetic position. Altogether, our results support the early divergence of Phylactolaemata from the rest of Bryozoa.