e Saccharomyces cerevisiae Doa4 deubiquitinating enzyme is required for the rapid degradation of protein substrates of the ubiquitin-proteasome pathway. Previous work suggested that Doa4 functions late in the pathway, possibly by deubiquitinating (poly)-ubiquitin-substrate intermediates associated with the 26S proteasome. We now provide evidence for physical and functional interaction between Doa4 and the proteasome. Genetic interaction is indicated by the mutual enhancement of defects associated with a deletion of DOA4 or a proteasome mutation when the two mutations are combined. Physical association of Doa4 and the proteasome was investigated with a new yeast 26S proteasome purification procedure, by which we find that a sizeable fraction of Doa4 copurifies with the protease. Another yeast deubiquitinating enzyme, Ubp5, which is related in sequence to Doa4 but cannot substitute for it even when overproduced, does not associate with the proteasome. DOA4-UBP5 chimeras were made by a novel PCR/yeast recombination method and used to identify an N-terminal 310-residue domain of Doa4 that, when appended to the catalytic domain of Ubp5, conferred Doa4 function, consistent with Ubp enzymes having a modular architecture. Unlike Ubp5, a functional Doa4-Ubp5 chimera associates with the proteasome, suggesting that proteasome binding is important for Doa4 function. Together, these data support a model in which Doa4 promotes proteolysis through removal of ubiquitin from proteolytic intermediates on the proteasome before or after initiation of substrate breakdown.