Hereditary spastic paraplegia (HSP) is characterized by progressive weakness and spasticity of the lower limbs due to degeneration of corticospinal axons. We found that patients from a chromosome 16q24.3-linked HSP family are homozygous for a 9.5 kb deletion involving a gene encoding a novel protein, named Paraplegin. Two additional Paraplegin mutations, both resulting in a frameshift, were found in a complicated and in a pure form of HSP. Paraplegin is highly homologous to the yeast mitochondrial ATPases, AFG3, RCA1, and YME1, which have both proteolytic and chaperon-like activities at the inner mitochondrial membrane. Immunofluorescence analysis and import experiments showed that Paraplegin localizes to mitochondria. Analysis of muscle biopsies from two patients carrying Paraplegin mutations showed typical signs of mitochondrial OXPHOS defects, thus suggesting a mechanism for neurodegeneration in HSP-type disorders.