Background The phylogenetic position of Bryozoa is one of the most controversial issues in metazoan phylogeny. In an attempt to address this issue, the first bryozoan mitochondrial genome from Flustrellidra hispida (Gymnolaemata, Ctenostomata) was recently sequenced and characterized. Unfortunately, it has extensive gene translocation and extremely reduced size. In addition, the phylogenies obtained from the result were conflicting, so they failed to assign a reliable phylogenetic position to Bryozoa or to clarify lophophorate phylogeny. Thus, it is necessary to characterize further mitochondrial genomes from slowly-evolving bryozoans to obtain a more credible lophophorate phylogeny. Results The complete mitochondrial genome (15,433 bp) of Bugula neritina (Bryozoa, Gymnolaemata, Cheilostomata), one of the most widely distributed cheliostome bryozoans, is sequenced. This second bryozoan mitochondrial genome contains the set of 37 components generally observed in other metazoans, differing from that of F. hispida (Bryozoa, Gymnolaemata, Ctenostomata), which has only 36 components with loss of tRNAser(ucn) genes. The B. neritina mitochondrial genome possesses 27 multiple noncoding regions. The gene order is more similar to those of the two remaining lophophorate phyla (Brachiopoda and Phoronida) and a chiton Katharina tunicate than to that of F. hispida. Phylogenetic analyses based on the nucleotide sequences or amino acid residues of 12 protein-coding genes showed consistently that, within the Lophotrochozoa, the monophyly of the bryozoan class Gymnolaemata (B. neritina and F. hispida) was strongly supported and the bryozoan clade was grouped with brachiopods. Echiura appeared as a subtaxon of Annelida, and Entoprocta as a sister taxon of Phoronida. The clade of Bryozoa + Brachiopoda was clustered with either the clade of Annelida-Echiura or that of Phoronida + Entoprocta. Conclusion This study presents the complete mitochondrial genome of a cheliostome bryozoan, B. neritina. The phylogenetic analyses suggest a close relationship between Bryozoa and Brachiopoda within the Lophotrochozoa. However, the sister group of Bryozoa + Brachiopoda is still ambiguous, although it has some attractions with Annelida-Echiura or Phoronida + Entoprocta. If the latter is a true phylogeny, lophophorate monophyly including Entoprocta is supported. Consequently, the present results imply that Brachiozoa (= Brachiopoda + Phoronida) and the recently-resurrected Bryozoa concept comprising Ectoprocta and Entoprocta may be refuted.