Parkin, an E3 ubiquitin ligase implicated in Parkinson's disease, promotes degradation of dysfunctional mitochondria by autophagy. Using proteomic and cellular approaches, we show that upon translocation to mitochondria, Parkin activates the ubiquitin–proteasome system (UPS) for widespread degradation of outer membrane proteins. This is evidenced by an increase in K48-linked polyubiquitin on mitochondria, recruitment of the 26S proteasome and rapid degradation of multiple outer membrane proteins. The degradation of proteins by the UPS occurs independently of the autophagy pathway, and inhibition of the 26S proteasome completely abrogates Parkin-mediated mitophagy in HeLa, SH-SY5Y and mouse cells. Although the mitofusins Mfn1 and Mfn2 are rapid degradation targets of Parkin, we find that degradation of additional targets is essential for mitophagy. These results indicate that remodeling of the mitochondrial outer membrane proteome is important for mitophagy, and reveal a causal link between the UPS and autophagy, the major pathways for degradation of intracellular substrates.