The phylogenetic relationships among certain groups of gastropods have remained unresolved in recent studies, especially in the diverse subclass Opisthobranchia, where nudibranchs have been poorly represented. Here we present the complete mitochondrial genomes of Melibe leonina and Tritonia diomedea (more recently named T. tetraquetra), two nudibranchs from the unrepresented Cladobranchia group, and report on the resulting phylogenetic analyses. Both genomes coded for the typical thirteen protein-coding genes, twenty-two transfer RNAs, and two ribosomal RNAs seen in other species. The twelve-nucleotide deletion previously reported for the cytochrome oxidase 1 gene in several other Melibe species was further clarified as three separate deletion events. These deletions were not present in any opisthobranchs examined in our study, including the newly sequenced M. leonina or T. diomedea, suggesting that these previously reported deletions may represent more recently divergent taxa. Analysis of the secondary structures for all twenty-two tRNAs of both M. leonina and T. diomedea indicated truncated d arms for the two serine tRNAs, as seen in some other heterobranchs. In addition, the serine 1 tRNA in T. diomedea contained an anticodon not yet reported in any other gastropod. For phylogenetic analysis, we used the thirteen protein-coding genes from the mitochondrial genomes of M. leonina, T. diomedea, and seventy-one other gastropods. Phylogenetic analyses were performed for both the class Gastropoda and the subclass Opisthobranchia. Both Bayesian and maximum likelihood analyses resulted in similar tree topologies. In the Opisthobranchia, the five orders represented in our study were monophyletic (Anaspidea, Cephalaspidea, Notaspidea, Nudibranchia, Sacoglossa). In Gastropoda, two of the three traditional subclasses, Opisthobranchia and Pulmonata, were not monophyletic. In contrast, four of the more recently named gastropod clades (Vetigastropoda, Neritimorpha, Caenogastropoda, and Heterobranchia) were all monophyletic, and thus appear to be better classifications for this diverse group.