The Caenorhabditis elegans synthetic multivulva (synMuv) genes act redundantly to antagonize the specification of vulval cell fates, which are promoted by an RTK/Ras pathway. At least 26 synMuv genes have been genetically identified, several of which encode proteins with homologs that act in chromatin remodeling or transcriptional repression. Here we report the molecular characterization of two synMuv genes, lin-37 and lin-54. We show that lin-37 and lin-54 encode proteins in a complex with at least seven synMuv proteins, including LIN-35, the only C. elegans homolog of the mammalian tumor suppressor Rb. Biochemical analyses of mutants suggest that LIN-9, LIN-53, and LIN-54 are required for the stable formation of this complex. This complex is distinct from a second complex of synMuv proteins with a composition similar to that of the mammalian Nucleosome Remodeling and Deacetylase complex. The class B synMuv complex we identified is evolutionarily conserved and likely functions in transcriptional repression and developmental regulation.