The Cancer Genome Atlas project has generated multi-dimensional and highly integrated genomic data from a large number of patient samples with detailed clinical records across many cancer types, but it remains unclear how to best integrate the massive amount of genomic data into clinical practice. We report here our methodology to build a multi-dimensional subnetwork atlas for cancer prognosis to better investigate the potential impact of multiple genetic and epigenetic (gene expression, copy number variation, microRNA expression and DNA methylation) changes on the molecular states of networks that in turn affects complex cancer survivorship. We uncover an average of 38 novel subnetworks in the protein-protein interaction network that correlate with prognosis across four prominent cancer types. The clinical utility of these subnetwork biomarkers was further evaluated by prognostic impact evaluation, functional enrichment analysis, drug target annotation, tumor stratification and independent validation. Some pathways including the dynactin, cohesion and pyruvate dehydrogenase-related subnetworks are identified as promising new targets for therapy in specific cancer types. In conclusion, this integrative analysis of existing protein interactome and cancer genomics data allows us to systematically dissect the molecular mechanisms that underlie unexpected outcomes for cancer, which could be used to better understand and predict clinical outcomes, optimize treatment and to provide new opportunities for developing therapeutics related to the subnetworks identified.