The genome is organized and packed into the nucleus through interactions with core histone proteins. Emerging evidence suggests that tumors are highly responsive to epigenetic alterations that induce chromatin-based events and dynamically influence tumor behavior. We examined chromatin organization in head and neck squamous cell carcinoma (HNSCC) using acetylation levels of histone 3 as a marker of chromatin compaction. Compared to control oral keratinocytes, we found that HNSCC cells are hypoacetylated and that microenvironmental cues (e.g., microvasculature endothelial cells) induce tumor acetylation. Furthermore, we found that chemical inhibition of histone deacetylases (HDAC) reduces the number of cancer stem cells (CSC) and inhibits clonogenic sphere formation. Paradoxically, inhibition of HDAC also induced epithelial-mesenchymal transition (EMT) in HNSCC cells, accumulation of BMI-1, an oncogene associated with tumor aggressiveness, and expression of the vimentin mesenchymal marker. Importantly, we observed co-expression of vimentin and acetylated histone 3 at the invasion front of human HNSCC tumor tissues. Collectively, these findings suggest that environmental cues, such as endothelial cell-secreted factors, modulate tumor plasticity by limiting the population of CSC and inducing EMT. Therefore, inhibition of HDAC may constitute a novel strategy to disrupt the population of CSC in head and neck tumors to create a homogeneous population of cancer cells with biologically defined signatures and predictable behavior.