The RUB1/NEDD-8 family of ubiquitin-related genes is widely represented among eukaryotes. Here we report that Cdc53p in Saccharomyces cerevisiae, a member of the Cullin family of proteins, is stably modified by the covalent attachment of a single Rub1p molecule. Two genes have been identified that are required for Rub1p conjugation to Cdc53p. The first gene, designated ENR2, encodes a protein with sequence similarity to the amino-terminal half of the ubiquitin-activating enzyme. By analogy with Aos1p, we infer that Enr2p functions in a bipartite Rub1p-activating enzyme. The second gene is SKP1, shown previously to be required for some ubiquitin-conjugation events. A deletion allele of ENR2 is lethal with temperature-sensitive alleles of cdc34 and enhances the phenotypes of cdc4, cdc53, and skp1, strongly implying that Rub1p conjugation to Cdc53p is required for optimal assembly or function of the E3 complex SCFCdc4. Consistent with this model, both enr2delta and an allele of Cdc53p that is not Rub1p modified, render cells sensitive to alterations in the levels of Cdc4p, Cdc34p, and Cdc53p.