c-Myc (Myc) is an important transcriptional regulator in embryonic stem (ES) cells, somatic cell reprogramming, and cancer. Here, we identify a Myc-centered regulatory network in ES cells by combining protein-protein and protein-DNA interaction studies and show that Myc interacts with the NuA4 complex, a regulator of ES cell identity. In combination with regulatory network information, we define three ES cell modules (Core, Polycomb, and Myc) and show that the modules are functionally separable, illustrating that the overall ES cell transcription program is composed of distinct units. With these modules as an analytical tool, we have reassessed the hypothesis linking an ES cell signature with cancer or cancer stem cells. We find that the Myc module, independent of the Core module, is active in various cancers and predicts cancer outcome. The apparent similarity of cancer and ES cell signatures reflects, in large part, the pervasive nature of Myc regulatory networks.