Histone modifications are thought to regulate gene expression in part by modulating DNA accessibility. Here, we measured genome-wide DNA accessibility in Drosophila melanogaster by combining M.SssI methylation footprinting with methylated DNA immunoprecipitation. We show that methylase accessibility demarcates differential distribution of active and repressive histone modifications as well as sites of transcription and replication initiation. DNA accessibility is increased at active promoters and chromosomal regions that are hyperacetylated at H4K16, particularly at the male X chromosome, suggesting that transcriptional dosage compensation is facilitated by permissive chromatin structure. Conversely, inactive chromosomal domains decorated with H3K27me3 are least accessible, supporting a model for Polycomb-mediated chromatin compaction. In addition, we detect higher accessibility at chromosomal regions that replicate early and at sites of replication initiation. Together, these findings indicate that differential histone-modification patterns and the organization of replication have distinct and measurable effects on the exposure of the DNA template.