Parkinson’s disease (PD) is the second most frequent neurodegenerative disease worldwide and the availability of early biomarkers and novel biotargets represents an urgent medical need. The main pathogenetic hallmark of PD is the specific loss of nigral dopaminergic neurons, in which mitochondrial dysfunction plays a crucial role. Mitochondrial proteases are central to the maintenance of healthy mitochondria and they have recently emerged as drug targets. However, an exhaustive characterization of these enzymes and their targets is still lacking, due to difficulties in analyzing proteolytic fragments by bottom-up proteomics approaches. Here, we propose the “mitochondrial dimethylation-TAILS” strategy, which combines the isolation of mitochondria with the enrichment of N-terminal peptides to analyze the mitochondrial N-terminome. We applied this method in a cellular model of altered dopamine homeostasis in neuroblastoma SH-SY5Y cells, which recapitulates early steps of PD pathogenesis. The main aim was to identify candidate mitochondrial proteases aberrantly activated by dopamine dysregulation and their cleaved targets. The proposed degradomics workflow was able to improve the identification of mitochondrial proteins if compared to classical shotgun analysis. In detail, 40% coverage of the mitochondrial proteome was obtained, the sequences of the transit peptides of two mitochondrial proteins were unveiled, and a consensus cleavage sequence for proteases involved in the processing of mitochondrial proteins was depicted. Mass spectrometry proteomics data have been submitted to ProteomeXchange with the identifier PXD013900. Moreover, sixty-one N-terminal peptides whose levels were affected by dopamine treatment were identified. By an in-depth analysis of the proteolytic peptides included in this list, eleven mitochondrial proteins showed altered proteolytic processing. One of these proteins (i.e., the 39S ribosomal protein L49 – MRPL49) was cleaved by the neprilysin protease, already exploited in clinics as a biotarget. We eventually demonstrated a mitochondrial subcellular localization of neprilysin in human cells for the first time. Collectively, these results shed new light on mitochondrial dysfunction linked to dopamine imbalance in PD and opened up the possibility to explore the mitochondrial targets of neprilysin as candidate biomarkers.