The 26 S proteasome is implicated in the control of many major biological functions but a reliable method for the identification of its major substrates, i.e. polyubiquitin (Ub) conjugates, is still lacking. Based on the steps present in cells, i.e. recognition and deubiquitination, we developed an affinity matrix-based purification of polyUb conjugates suitable for any biological sample. Ub-conjugates were first purified from proteasome inhibitor-treated C2C12 cells using the Ub binding domains of the S5a proteasome subunit bound to an affinity matrix and then deubiquitinated by the catalytic domain of the USP2 enzyme. This two step purification of proteasome substrates involving both protein-protein interactions and enzyme-mediated release allowed highly specific isolation of polyUb 26 S proteasome substrates, which were then resolved on two-dimensional gels post-deubiquitination. To establish our method, we focused on a gel area where spots were best resolved. Surprisingly, spot analysis by mass spectrometry identified alpha2, alpha6, alpha7, beta2, beta3, beta4, and beta5 20 S proteasome subunits as potential substrates. Western blots using an anti-beta3 proteasome subunit antibody confirmed that high molecular weight forms of beta3 were present, particularly in proteasome inhibitor-treated cells. Sucrose gradients of cell lysates suggested that the proteasome was first disassembled before subunits were polyubiquitinated. Altogether, we provide a technique that enables large scale identification of 26 S proteasome substrates that should contribute to a better understanding of this proteolytic machinery in any living cell and/or organ/tissue. Furthermore, the data suggest that proteasome homeostasis involves an autoregulatory mechanism.