The discovery of pathways and regulatory networks whose perturbation contributes to neoplastic transformation remains a fundamental challenge for cancer biology. We show that such pathway perturbations, and the cis-regulatory elements through which they operate, can be efficiently extracted from global gene expression profiles. Our approach utilizes information-theoretic analysis of expression levels, pathways, and genomic sequences. Analysis across a diverse set of human cancers reveals the majority of previously known cancer pathways. Through de novo motif discovery we associate these pathways with transcription-factor binding sites and miRNA targets, including those of E2F, NF-Y, p53, and let-7. Follow-up experiments confirmed that these predictions correspond to functional in vivo regulatory interactions. Strikingly, the majority of the perturbations, associated with putative cis-regulatory elements, fall outside of known cancer pathways. Our study provides a systems-level dissection of regulatory perturbations in cancer—an essential component of a rational strategy for therapeutic intervention and drug-target discovery.