Memory lymphocytes are characterized by their ability to exhibit a rapid response to the recall antigen, in which differential transcription is important, yet the underlying mechanism is not understood. We report here a genome-wide analysis of histone methylation on two histone H3 lysine residues (H3K4me3 and H3K27me3) and gene expression profiles in naive and memory CD8(+) T cells. We found that specific correlation exists between gene expression and the amounts of H3K4me3 (positive correlation) and H3K27me3 (negative correlation) across the gene body. These correlations displayed four distinct modes (repressive, active, poised, and bivalent), reflecting different functions of these genes in CD8(+) T cells. Furthermore, a permissive chromatin state of each gene was established by a combination of different histone modifications. Our findings reveal a complex regulation by histone methylation in differential gene expression and suggest that histone methylation may be responsible for memory CD8(+) T cell function.