The ubiquitin ligase Mdm2 targets the p53 tumor suppressor protein for proteasomal degradation. Mutating phosphorylation sites in the central domain of Mdm2 prevents p53 degradation, although it is still ubiquitylated, indicating that Mdm2 has a post-ubiquitylation function for p53 degradation. We show that Mdm2 associates with several subunits of the 19S proteasome regulatory particle in a ubiquitylation-independent manner. Mdm2 furthermore promotes the formation of a ternary complex of itself, p53, and the proteasome. Replacing phosphorylation sites within the central domain with alanines reduced the formation of the ternary complex. The C-terminus of Mdm2 was sufficient for interaction with the proteasome despite an additional proteasome binding site in the Mdm2 N-terminus. In addition to binding to the proteasome, the C-terminus of Mdm2 bound to the central domain, possibly competing with, and therefore blocking, Mdm2/proteasome interaction. We propose that Mdm2 facilitates, or at least enhances, the association of p53 with the proteasome and that phosphorylation of the central domain of Mdm2 regulates this process.