Various liver diseases, including hepatocellular carcinoma (HCC), have been linked to mitochondrial dysfunction, a condition characterized by abnormal levels of nitric oxide (NO) and reactive oxygen species (ROS). In this study, we subjected the human liver mitochondrial proteome to an extensive quantitative proteomic profiling analysis and molecular characterization to identify potential signatures indicative of cancer cell growth and progression. A sequential proteomic analysis identified 2452 mitochondrial proteins, of which 1464 and 2010 were classified as normal and HCC mitochondrial proteins, respectively, with 1022 overlaps. Further metabolic mapping of the HCC mitochondrial proteins narrowed our biological characterization to four proteins, namely ALDH4A1, LRPPRC, ATP5C1 and ALDH6A1. The latter protein, a mitochondrial methylmalonate semialdehyde dehydrogenase (ALDH6A1), was most strongly suppressed in HCC tumor regions (~10-fold decrease) and was predicted to present in plasma. Accordingly, we selected ALDH6A1 for a functional analysis. Interestingly, much lower NO levels were detected in both HCC tumor regions and an ALDH6A1-overexpression (O/E) cell line than in control (Hep3B) cells and could be restored by treatment with S-nitroso-N-acetyl-penicillamine. In contrast, ALDH6A1-O/E cells exhibited an approximately 50% increase in ROS levels and decreased lactate levels relative to control cells. Propidium iodine staining suggested that the abnormal decrease in NO and increase in ROS could be caused by depolarization of the mitochondrial membrane potential (ΔΨ). We propose that an attenuated ALDH6A1 level may subsequently promote uncontrolled cell growth and proliferation, act as a signature for assessing HCC progression and treatment responses.