The structural unit of eukaryotic chromatin is a nucleosome, comprising two histone H2A-H2B heterodimers and one histone (H3-H4)2 tetramer, wrapped around by ∼146 bp of DNA. The N-terminal flexible histone tails stick out from the histone core and have extensive posttranslational modifications, causing epigenetic changes of chromatin. Although crystal and cryogenic electron microscopy structures of nucleosomes are available, the flexible tail structures remain elusive. Using NMR, we have examined the dynamics of histone H3 tails in nucleosomes containing unmodified and tetra-acetylated H4 tails. In unmodified nucleosome, the H3 tail adopts a dynamic equilibrium structure between DNA-contact and reduced-contact states. In acetylated H4 nucleosome, however, the H3 tail equilibrium shifts to a mainly DNA-contact state with a minor reduced-contact state. The acetylated H4 tail is dynamically released from its own DNA-contact state to a reduced-contact state, while the H3 tail DNA-contact state becomes major. Notably, H3 K14 in the acetylated H4 nucleosome is much more accessible to acetyltransferase Gcn5 relative to unmodified nucleosome, possibly due to the formation of a favorable H3 tail conformation for Gcn5. In summary, each histone tail adopts a characteristic dynamic state but regulates one other, probably creating a histone tail network even on a nucleosome.