The PARKIN ubiquitin ligase (also known as PARK2) and its regulatory kinase PINK1 (also known as PARK6), often mutated in familial early-onset Parkinson's disease, have central roles in mitochondrial homeostasis and mitophagy. Whereas PARKIN is recruited to the mitochondrial outer membrane (MOM) upon depolarization via PINK1 action and can ubiquitylate porin, mitofusin and Miro proteins on the MOM, the full repertoire of PARKIN substrates--the PARKIN-dependent ubiquitylome--remains poorly defined. Here we use quantitative diGly capture proteomics (diGly) to elucidate the ubiquitylation site specificity and topology of PARKIN-dependent target modification in response to mitochondrial depolarization. Hundreds of dynamically regulated ubiquitylation sites in dozens of proteins were identified, with strong enrichment for MOM proteins, indicating that PARKIN dramatically alters the ubiquitylation status of the mitochondrial proteome. Using complementary interaction proteomics, we found depolarization-dependent PARKIN association with numerous MOM targets, autophagy receptors, and the proteasome. Mutation of the PARKIN active site residue C431, which has been found mutated in Parkinson's disease patients, largely disrupts these associations. Structural and topological analysis revealed extensive conservation of PARKIN-dependent ubiquitylation sites on cytoplasmic domains in vertebrate and Drosophila melanogaster MOM proteins. These studies provide a resource for understanding how the PINK1-PARKIN pathway re-sculpts the proteome to support mitochondrial homeostasis.