In eukaryotic cells, intracellular protein breakdown is mainly performed by the ubiquitin–proteasome system. Proteasomes are supramolecular protein complexes formed by the association of multiple sub-complexes and interacting proteins. Therefore, they exhibit a very high heterogeneity whose function is still not well understood. Here, using a newly 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 subtypes, 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 broadly applied for unraveling the dynamic and heterogeneous nature of other biologically relevant supramolecular protein complexes.