Proteolysis plays an important role in mitochondrial biogenesis, from the processing of newly imported precursor proteins to the degradation of mitochondrial targeting peptides. Disruption of peptide degradation activity in yeast, plant and mammalian mitochondria is known to have deleterious consequences for organism physiology, highlighting the important role of mitochondrial peptidases. In the present work, we show that the human mitochondrial peptidase neurolysin (hNLN) can degrade mitochondrial presequence peptides as well as other fragments up to 19 amino acids long. The crystal structure of hNLNE475Q in complex with the products of neurotensin cleavage at 2.7 Å revealed a closed conformation with an internal cavity that restricts substrate length and highlighted the mechanism of enzyme opening/closing that is necessary for substrate binding and catalytic activity. Analysis of peptide degradation in vitro showed that hNLN cooperates with presequence protease (PreP or PITRM1) in the degradation of long targeting peptides and amyloid-β peptide, Aβ1–40, associated with Alzheimer disease, particularly cleaving the hydrophobic fragment Aβ35–40. These findings suggest that a network of proteases may be required for complete degradation of peptides localized in mitochondria.