The m-AAA protease, an ATP-dependent proteolytic complex in the mitochondrial inner membrane, controls protein quality and regulates ribosome assembly, thus exerting essential housekeeping functions within mitochondria. Mutations in the m-AAA protease subunit paraplegin cause axonal degeneration in hereditary spastic paraplegia (HSP), but the basis for the unexpected tissue specificity is not understood. Paraplegin assembles with homologous Afg3l2 subunits into hetero-oligomeric complexes which can substitute for yeast m-AAA proteases, demonstrating functional conservation. The function of a third paralogue, Afg3l1 expressed in mouse, is unknown. Here, we analyze the assembly of paraplegin into m-AAA complexes and monitor consequences of paraplegin deficiency in HSP fibroblasts and in a mouse model for HSP. Our findings reveal variability in the assembly of m-AAA proteases in mitochondria in different tissues. Homo-oligomeric Afg3l1 and Afg3l2 complexes and hetero-oligomeric assemblies of both proteins with paraplegin can be formed. Yeast complementation studies demonstrate the proteolytic activity of these assemblies. Paraplegin deficiency in HSP does not result in the loss of m-AAA protease activity in brain mitochondria. Rather, homo-oligomeric Afg3l2 complexes accumulate, and these complexes can substitute for housekeeping functions of paraplegin-containing m-AAA complexes. We therefore propose that the formation of m-AAA proteases with altered substrate specificities leads to axonal degeneration in HSP.