The mitochondrial m-AAA protease has a crucial role in axonal development and maintenance. Human mitochondria possess two m-AAA protease isoenzymes: a hetero-oligomeric complex, composed of paraplegin and AFG3L2 (Afg3 like 2), and a homo-oligomeric AFG3L2 complex. Loss of function of paraplegin (encoded by the SPG7 gene) causes hereditary spastic paraplegia, a disease characterized by retrograde degeneration of cortical motor axons. Spg7−/− mice show a late-onset degeneration of long spinal and peripheral axons with accumulation of abnormal mitochondria. In contrast, Afg3l2Emv66/Emv66 mutant mice, lacking the AFG3L2 protein, are affected by a severe neuromuscular phenotype, due to defects in motor axon development. The role of the homo-oligomeric m-AAA protease and the extent of cooperation and redundancy between the two isoenzymes in adult neurons are still unclear. Here we report an early-onset severe neurological phenotype in Spg7−/−Afg3l2Emv66/+ mice, characterized by loss of balance, tremor and ataxia. Spg7−/−Afg3l2Emv66/+ mice display acceleration and worsening of the axonopathy observed in paraplegin-deficient mice. In addition, they show prominent cerebellar degeneration with loss of Purkinje cells and parallel fibers, and reactive astrogliosis. Mitochondria from affected tissues are prone to lose mt-DNA and have unstable respiratory complexes. At late stages, neurons contain structural abnormal mitochondria defective in COX-SDH reaction. Our data demonstrate genetic interaction between the m-AAA isoenzymes and suggest that different neuronal populations have variable thresholds of susceptibility to reduced levels of the m-AAA protease. Moreover, they implicate impaired mitochondrial proteolysis as a novel pathway in cerebellar degeneration.