Our recent studies have provided a proteomic blueprint of the 26S proteasome complexes in the heart, among which 20S proteasomes were found to contain cylinder-shaped structures consisting of both α and β subunits. These proteasomes exhibit a number of features unique to the myocardium, including striking differences in post-translational modifications (PTMs) of individual subunits and novel PTMs that have not been previously reported. To date, mechanisms contributing to the regulation of this myocardial proteolytic core system remain largely undefined; in particular, little is known regarding PTM-dependent regulation of cardiac proteasomes. In this investigation, we seek to elucidate the function and regulation of 20S proteasome complexes in the heart. Functionally viable murine cardiac 20S proteasomes were purified. Tandem mass spectrometry analyses, combined with native gel electrophoresis, immunoprecipitation, and immunoblotting, revealed the identification of 2 previously unrecognized functional partners in the endogenous intact cardiac 20S complexes: protein phosphatase 2A (PP2A), and protein kinase A (PKA). Furthermore, our results demonstrated that PP2A and PKA profoundly impact the proteolytic function of 20S proteasomes: phosphorylation of 20S complexes enhances the peptidase activity of individual subunits in a substrate-specific fashion. Moreover, inhibition of PP2A or the addition of PKA significantly modified both the serine- and threonine-phosphorylation profile of proteasomes; multiple individual subunits of 20S (eg, α1 and β2) were targets of PP2A and PKA. Taken together, these studies provide the first demonstration that the function of cardiac 20S proteasomes is modulated by associating partners and that phosphorylation may serve as a key mechanism for regulation.