PINK1 is a mitochondrial kinase mutated in some familial cases of Parkinson’s disease. It has been found to work in the same pathway as the E3 ligase Parkin in the maintenance of flight muscles and dopaminergic neurons in Drosophila melanogaster and to recruit cytosolic Parkin to mitochondria to mediate mitophagy in mammalian cells. Although PINK1 has a predicted mitochondrial import sequence, its cellular and submitochondrial localization remains unclear in part because it is rapidly degraded. In this study, we report that the mitochondrial inner membrane rhomboid protease presenilin-associated rhomboid-like protein (PARL) mediates cleavage of PINK1 dependent on mitochondrial membrane potential. In the absence of PARL, the constitutive degradation of PINK1 is inhibited, stabilizing a 60-kD form inside mitochondria. When mitochondrial membrane potential is dissipated, PINK1 accumulates as a 63-kD full-length form on the outer mitochondrial membrane, where it can recruit Parkin to impaired mitochondria. Thus, differential localization to the inner and outer mitochondrial membranes appears to regulate PINK1 stability and function.