The labrid tribe Odacini comprises four genera and 12 species of fishes that inhabit shallow kelp forest and seagrass areas in temperate waters of Australia and New Zealand. Odacines are morphologically disparate, but share synapomorphies in fin structure and fusion of teeth into a beak-like oral jaw. A phylogenetic analysis of odacines was conducted to investigate their relationships to other labrid fishes, the relationships of species within the tribe, and the evolution of herbivory within the group. Fragments from two mitochondrial genes, 12S rDNA and 16S rDNA, and two nuclear genes, Tmo4C4 and RAG2, were sequenced for seven odacine species (representing all four genera), eight species representing the other major labrid lineages, and three outgroup species. Maximum likelihood and maximum parsimony analyses on the resulting 2338 bp of DNA sequence produced nearly identical topologies differing only in the placement of a clade containing the cheiline Cheilinus fasciatus and the scarine Cryptotomus roseus. The remaining clades received strong bootstrap support under maximum parsimony, and all clades in the maximum likelihood analysis received high bootstrap proportions and high posterior probabilities. The hypsigenyine labrid Choerodon anchorago formed the sister group to the odacines. Within the odacines, Odax cyanoallix+Odax pullus formed the sister to the remaining odacines, with Odax acroptilus, Odax cyanomelas, and Siphonognathus argyrophanes forming successively closer sister groups to the clade Haletta semifasciatus+Neoodax balteatus. Either herbivory evolved twice in the odacines, or herbivory evolved once with two reversions to carnivory. The latter hypothesis appears more likely in the light of odacine feeding biology.