DNA cytosine methylation regulates gene expression in mammals. In bacteria, its role in gene expression and genome architecture is less understood. Here we perform high-throughput sequencing of bisulfite-treated genomic DNA from Escherichia coli K12 to describe, for the first time, the extent of cytosine methylation of bacterial DNA at single-base resolution. Whereas most target sites (C(m)CWGG) are fully methylated in stationary phase cells, many sites with an extended CC(m)CWGG motif are only partially methylated in exponentially growing cells. We speculate that these partially methylated sites may be selected, as these are slightly correlated with the risk of spontaneous, non-synonymous conversion of methylated cytosines to thymines. Microarray analysis in a cytosine methylation-deficient mutant of E. coli shows increased expression of the stress response sigma factor RpoS and many of its targets in stationary phase. Thus, DNA cytosine methylation is a regulator of stationary phase gene expression in E. coli.