Deficiency of the sulfide metabolizing protein ETHE1 is the cause of ethylmalonic encephalopathy (EE), an inherited and severe metabolic disorder. To study the molecular effects of EE, we performed a proteomics study on mitochondria from cultured patient fibroblast cells. Samples from six patients were analyzed and revealed seven differentially regulated proteins compared with healthy controls. Two proteins involved in pathways of detoxification and oxidative/reductive stress were underrepresented in EE patient samples: mitochondrial superoxide dismutase (SOD2) and aldehyde dehydrogenase X (ALDH1B). Sulfide:quinone oxidoreductase (SQRDL), which takes part in the same sulfide pathway as ETHE1, was also underrepresented in EE patients. The other differentially regulated proteins were apoptosis inducing factor (AIFM1), lactate dehydrogenase (LDHB), chloride intracellular channel (CLIC4) and dimethylarginine dimethylaminohydrolase 1 (DDAH1). These proteins have been reported to be involved in encephalopathy, energy metabolism, ion transport, and nitric oxide regulation, respectively. Interestingly, oxidoreductase activity was overrepresented among the regulated proteins indicating that redox perturbation plays an important role in the molecular mechanism of EE. This observation may explain the wide range of symptoms associated with the disease, and highlights the potency of the novel gaseous mediator sulfide.