In mammalian cells, the 26S proteasomes vary in composition. In addition to the standard 28 subunits in the 20S core particle and 19 subunits in each 19S regulatory particle, a small fraction (about 10–20% in our preparations) also contains the deubiquitinating enzyme Usp14/Ubp6, which regulates proteasome activity, and the ubiquitin ligase, Ube3c/Hul5, which enhances proteasomal processivity. When degradation of ubiquitinated proteins in cells was inhibited, levels of Usp14 and Ube3c on proteasomes increased within minutes. Conversely, when protein ubiquitination was prevented, or when purified proteasomes hydrolyzed the associated ubiquitin conjugates, Usp14 and Ube3c dissociated rapidly (unlike other 26S subunits), but the inhibitor ubiquitin aldehyde slowed their dissociation. Recombinant Usp14 associated with purified proteasomes preferentially if they contained ubiquitin conjugates. In cells or extracts, adding Usp14 inhibitors (IU-1 or ubiquitin aldehyde) enhanced Usp14 and Ube3c binding further. Thus, in the substrate- or the inhibitor-bound conformations, Usp14 showed higher affinity for proteasomes and surprisingly enhanced Ube3c binding. Moreover, adding ubiquitinated proteins to cell extracts stimulated proteasome binding of both enzymes. Thus, Usp14 and Ube3c cycle together on and off proteasomes, and the presence of ubiquitinated substrates promotes their association. This mechanism enables proteasome activity to adapt to the supply of substrates.