Many forms of cancer have multiple subtypes with different causes and clinical outcomes. Somatic tumor genomes provide a rich new source of data for uncovering these subtypes but have proven difficult to compare as two tumors rarely share the same mutations. Here, we introduce a method called Network Based Stratification (NBS) which integrates somatic tumor genomes with gene networks. This approach allows for stratification of cancer into informative subtypes by clustering together patients with mutations in similar network regions. We demonstrate NBS in ovarian, uterine and lung cancer cohorts from The Cancer Genome Atlas. For each tissue, NBS identifies clear subtypes that are predictive of clinical outcomes such as patient survival, response to therapy or tumor histology. We identify network regions characteristic of each subtype and show how mutation-derived subtypes can be used to train an mRNA expression signature which provides similar information in the absence of DNA sequence.