Here, we used an informatics-based approach to identify novel biomarkers of overall survival and tumor progression in non-small cell lung cancer (NSCLC) patients. We determined whether nuclear-encoded genes associated with mitochondrial biogenesis and function can be used to effectively predict clinical outcome in lung cancer. This strategy allowed us to directly provide in silico validation of the prognostic value of these mitochondrial components in large, clinically-relevant, lung cancer patient populations. Towards this end, we used a group of 726 lung cancer patients, with negative surgical margins. Importantly, in this group of cancer patients, markers of cell proliferation (Ki67 and PCNA) were associated with poor overall survival, as would be expected. Similarly, key markers of inflammation (CD163 and CD68) also predicted poor clinical outcome in this patient population. Using this approach, we identified >180 new individual mitochondrial gene probes that effectively predicted significantly reduced overall survival, with hazard-ratios (HR) of up to 4.89 (p<1.0e-16). These nuclear-encoded mitochondrial genes included chaperones, membrane proteins as well as ribosomal proteins (MRPs) and components of the OXPHOS (I-V) complexes. In this analysis, HSPD1, a key marker of mitochondrial biogenesis, had the highest predictive value and was also effective in predicting tumor progression in both smokers and non-smokers alike. In fact, it had even higher predictive value in non-smokers (HR=5.9; p=3.9e-07). Based on this analysis, we conclude that mitochondrial biogenesis should be considered as a new therapeutic target, for the more effective treatment of human lung cancers. The mitochondrial biomarkers that we have identified could serve as new companion diagnostics to assist clinicians in more accurately predicting clinical outcomes in lung cancer patients, driving more personalized cancer therapy.