Mmutations in paraplegin, a putative mitochondrial metallopeptidase of the AAA family, cause an autosomal recessive form of hereditary spastic paraplegia (HSP). Here, we analyze the function of paraplegin at the cellular level and characterize the phenotypic defects of HSP patients' cells lacking this protein. We demonstrate that paraplegin coassembles with a homologous protein, AFG3L2, in the mitochondrial inner membrane. These two proteins form a high molecular mass complex, which we show to be aberrant in HSP fibroblasts. The loss of this complex causes a reduced complex I activity in mitochondria and an increased sensitivity to oxidant stress, which can both be rescued by exogenous expression of wild-type paraplegin. Furthermore, complementation studies in yeast demonstrate functional conservation of the human paraplegin–AFG3L2 complex with the yeast m-AAA protease and assign proteolytic activity to this structure. These results shed new light on the molecular pathogenesis of HSP and functionally link AFG3L2 to this neurodegenerative disease.