Background: Multi-omics analyses are profitable for discovering novel biomarkers and drug targets, but such integrated examinations on mitochondria of colorectal cancer (CRC) patients are lacking. Methods: We investigated global structural variants, DNA methylation, chromatin accessibility, proteome, and phosphoproteome on human CRC (n = 6-8). The alterations of mitochondria on these levels and potential upstream regulatory genes were described. Furthermore, combining with the mRNA datasets of 538 CRC and 91 colitis patients from the public databases, we identified independent prognostic factors (IPFs). Findings: Revealed by the proteogenomic analyses in our study, mitochondria altered the most among all organelles in CRC, which were also associated with patient prognosis the most. We found that the mRNA of one nuclear-coding mitochondrial gene (NCMG), HIGD1A, decreased in colitis, two subtypes of adenoma, and six subtypes of CRC, subsequently was identified as a favorable IPF for CRC. Besides, the comprehensive analyses of mitochondria by multi-omics uncovered unique proteogenomic alterations on six survival-related NCMGs. Key transcriptional factors potentially regulating the mitochondria were also unveiled, such as GLIS1, JUN, CREB1, and YAP1. Finally, p38 was highlighted as one possible central kinase involving in the modulation of mitochondrial activity in CRC patients. Interpretation: Our study presents a multilayer and molecular picture of mitochondria of CRC patients, recognizes HIGD1A as a potential prognostic biomarker, and provides new candidate genes as therapeutic targets.