A library of random 10 residue peptides fused to the N-terminus of a reporter protein was screened in the yeast Saccharomyces cerevisiae for sequences that can target the reporter for degradation by the N-end rule pathway, a ubiquitin (Ub)-dependent proteolytic system that recognizes potential substrates through binding to their destabilizing N-terminal residues. One of the N-terminal sequences identified by this screen was used in a second screen for mutants incapable of degrading the corresponding reporter fusion. A mutant thus identified had an abnormally low content of free Ub. This mutant was found to be allelic to a previously isolated mutant in a Ub-dependent proteolytic system distinct from the N-end rule pathway. We isolated the gene involved, termed UFD3, which encodes an 80 kDa protein containing tandem repeats of a motif that is present in many eukaryotic proteins and called the WD repeat. Both co-immunoprecipitation and two-hybrid assays demonstrated that Ufd3p is an in vivo ligand of Cdc48p, an essential ATPase required for the cell cycle progression and the fusion of endoplasmic reticulum membranes. Further, we showed that, similarly to Ufd3p, Cdc48p is also required for the Ub-dependent proteolysis of test substrates. The discovery of the Ufd3p--Cdc48p complex and the finding that this complex is a part of the Ub system open up a new direction for studies of the function of Ub in the cell cycle and membrane dynamics.