NuA4, the major H4 lysine acetyltransferase (KAT) complex in Saccharomyces cerevisiae, is recruited to promoters and stimulates transcription initiation. NuA4 subunits contain domains that bind methylated histones, suggesting that histone methylation should target NuA4 to coding sequences during transcription elongation. We show that NuA4 is cotranscriptionally recruited, dependent on its physical association with elongating polymerase II (Pol II) phosphorylated on the C-terminal domain by cyclin-dependent kinase 7/Kin28, but independently of subunits (Eaf1 and Tra1) required for NuA4 recruitment to promoters. Whereas histone methylation by Set1 and Set2 is dispensable for NuA4's interaction with Pol II and targeting to some coding regions, it stimulates NuA4-histone interaction and H4 acetylation in vivo. The NuA4 KAT, Esa1, mediates increased H4 acetylation and enhanced RSC occupancy and histone eviction in coding sequences and stimulates the rate of transcription elongation. Esa1 cooperates with the H3 KAT in SAGA, Gcn5, to enhance these functions. Our findings delineate a pathway for acetylation-mediated nucleosome remodeling and eviction in coding sequences that stimulates transcription elongation by Pol II in vivo.