Heterochromatin is believed to be associated with increased levels of cytosine methylation. With the recent availability of genome-wide, high-resolution molecular data reflecting chromatin organization and methylation, such relationships can be explored systematically. As well-defined surrogates for heterochromatin, we tested the relationship between DNA replication timing and DNase hypersensitivity with cytosine methylation in two human cell types, unexpectedly finding the later-replicating, more heterochromatic regions to be less methylated than early replicating regions. When we integrated gene-expression data into the study, we found that regions of increased gene expression were earlier replicating, as previously identified, and that transcription-targeted cytosine methylation in gene bodies contributes to the positive correlation with early replication. A self-organizing map (SOM) approach was able to identify genomic regions with early replication and increased methylation, but lacking annotated transcripts, loci missed in simple two variable analyses, possibly encoding unrecognized intergenic transcripts. We conclude that the relationship of cytosine methylation with heterochromatin is not simple and depends on whether the genomic context is tandemly repetitive sequences often found near centromeres, which are known to be heterochromatic and methylated, or the remaining majority of the genome, where cytosine methylation is targeted preferentially to the transcriptionally active, euchromatic compartment of the genome.