Intracellular protein breakdown is mainly performed by the Ubiquitin-Proteasome System in eukaryotic cells. Proteasomes are supramolecular protein complexes formed by the association of multiple sub-complexes and interacting proteins. They thus exhibit a very high heterogeneity whose function still needs to be understood. Here, using a new developed method based on the combination of affinity purification and protein correlation profiling associated with high resolution mass spectrometry, we comprehensively characterized proteasome heterogeneity and identified previously unknown preferential associations within proteasome sub-complexes. In particular, we showed for the first time that the two main proteasome sub-types, standard proteasome and immunoproteasome, interact with a different subset of important regulators. This trend was observed in very diverse human cell types and was confirmed by changing the relative proportions of both 20S proteasome forms using interferon-γ. The new method developed here constitutes an innovative and powerful strategy that could be widened to unravel the dynamic and heterogeneous nature of many other biologically relevant molecular systems.