Eusocial insects organize themselves into behavioral castes whose regulation has been proposed to involve epigenetic processes, including histone modification. In the carpenter ant Camponotus floridanus, morphologically distinct worker castes called minors and majors exhibit pronounced differences in foraging and scouting behaviors. We found that these behaviors are regulated by histone acetylation likely catalyzed by the conserved acetyltransferase CBP. Transcriptome and chromatin analysis in brains of scouting minors fed pharmacological inhibitors of CBP and histone deacetylases (HDACs) revealed hundreds of genes linked to hyperacetylated regions targeted by CBP. Majors rarely forage, but injection of a HDAC inhibitor or small interfering RNAs against the HDAC Rpd3 into young major brains induced and sustained foraging in a CBP-dependent manner. Our results suggest that behavioral plasticity in animals may be regulated in an epigenetic manner via histone modification.