Predicting biotic resistance to highly invasive strains of “killer algae” (Caulerpa spp.) requires understanding the diversity and feeding preferences of native consumers, including sea slugs in family Oxynoidae. Past studies reported low algal host specificity for Oxynoe (6 spp.) and Lobiger (4 spp.), but these taxonomically challenging slugs may represent species complexes of unrecognized specialists that prefer different Caulerpa spp. Here, we assess global diversity of these genera by integrating gene sequences with morphological data from microscopic teeth and internal shells, the only hard parts in these soft-bodied invertebrates. Four delimitation methods applied to datasets comprising mtDNA and/or nuclear alleles yielded up to 16 species hypotheses for samples comprising five nominal taxa, including five highly divergent species in Lobiger and five in Oxynoe. Depending on the analysis, a further four to six species were recovered in the O. antillarum-viridis complex, a clade in which mitochondrial divergence was low and nuclear alleles were shared among lineages. Bayesian species delimitation using only morphological data supported most candidate species, however, and integrative analyses combining morphological and genetic data fully supported all complex members. Collectively, our findings double the recognized biodiversity in Oxynoidae, and illustrate the value of including data from traits that mediate fast-evolving ecological interactions during species delimitation. Preference for Caulerpa spp. and radular tooth characteristics covaried among newly delimited species, highlighting an unappreciated degree of host specialization and coevolution in these taxa that may help predict their role in containing outbreaks of invasive algae.