There is a need to identify genetic mediators of solid-tumor cancers, such as prostate cancer, where invasion and distant metastases determine the clinical outcome of the disease. Whole-genome expression profiling offers promise in this regard, but can be complicated by the challenge of identifying the genes affected by a condition from the hundreds to thousands of genes that exhibit changes in expression. Here, we show that reverse-engineered gene networks can be combined with expression profiles to compute the likelihood that genes and associated pathways are mediators of a disease. We apply our method to non-recurrent primary and metastatic prostate cancer data, and identify the androgen receptor gene (AR) among the top genetic mediators and the AR pathway as a highly enriched pathway for metastatic prostate cancer. These results were not obtained on the basis of expression change alone. We further demonstrate that the AR gene, in the context of the network, can be used as a marker to detect the aggressiveness of primary prostate cancers. This work shows that a network biology approach can be used advantageously to identify the genetic mediators and mediating pathways associated with a disease.