Nematodes of the suborder Cephalobina include an ecologically and morphologically diverse array of species that range from soil-dwelling microbivores to parasites of vertebrates and invertebrates. Despite a long history of study, certain of these microbivores (Cephaloboidea) present some of the most intractable problems in nematode systematics; the lack of an evolutionary framework for these taxa has prevented the identification of natural groups and inhibited understanding of soil biodiversity and nematode ecology. Phylogenetic analyses of ribosomal (LSU) sequence data from 53 taxa revealed strong support for monophyly of taxa representing the Cephaloboidea, but do not support the monophyly of most genera within this superfamily. Historically these genera have primarily been recognized based on variation in labial morphology, but molecular phylogenies show the same general labial (probolae) morphotype often results from recurrent similarity, a result consistent with the phenotypic plasticity of probolae previously observed for some species in ecological time. Phylogenetic analyses of LSU rDNA also recovered strong support for some other groups of cephalobs, including taxa representing most (but not all) Panagrolaimoidea. In addition to revealing homoplasy of probolae, molecular trees also imply other unexpected patterns of character evolution or polarity, including recurrent similarity of offset spermatheca presence, and representation of complex probolae as the ancestral condition within Cephaloboidea. For Cephalobidae, molecular trees do not support traditional genera as natural groups, but it remains untested if deconstructing probolae morphotypes or other structural features into finer component characters may reveal homologies that help delimit evolutionary lineages.