Mitochondrial proteases are key components in mitochondrial stress responses that maintain proteostasis and mitochondrial integrity in harsh environmental conditions, which leads to the acquisition of aggressive phenotypes, including chemoresistance and metastasis. However, the molecular mechanisms and exact role of mitochondrial proteases in cancer remain largely unexplored. Here, we identified functional crosstalk between LONP1 and ClpP, which are two mitochondrial matrix proteases that cooperate to attenuate proteotoxic stress and protect mitochondrial functions for cancer cell survival. LONP1 and ClpP genes closely localized on chromosome 19 and were co-expressed at high levels in most human cancers. Depletion of both genes synergistically attenuated cancer cell growth and induced cell death due to impaired mitochondrial functions and increased oxidative stress. Using mitochondrial matrix proteomic analysis with an engineered peroxidase (APEX)-mediated proximity biotinylation method, we identified the specific target substrates of these proteases, which were crucial components of mitochondrial functions, including oxidative phosphorylation, the TCA cycle, and amino acid and lipid metabolism. Furthermore, we found that LONP1 and ClpP shared many substrates, including serine hydroxymethyltransferase 2 (SHMT2). Inhibition of both LONP1 and ClpP additively increased the amount of unfolded SHMT2 protein and enhanced sensitivity to SHMT2 inhibitor, resulting in significantly reduced cell growth and increased cell death under metabolic stress. Additionally, prostate cancer patients with higher LONP1 and ClpP expression exhibited poorer survival. These results suggest that interventions targeting the mitochondrial proteostasis network via LONP1 and ClpP could be potential therapeutic strategies for cancer.