All-trans-retinoic acid (RA) is a vitamin A metabolite that plays major roles in regulating stem cell differentiation and development. RA is the ligand of the retinoic acid receptor (RAR) family of transcription factors, which interact with retinoic acid response elements (RAREs) within target gene proximal promoters and enhancers. Although RA-mediated gene activation is well understood, less is known about the mechanisms for repression at RA-regulated genes. Using chromatin immunoprecipitation experiments, we show that in embryonic stem cells in the absence of RA, histone deacetylases (HDACs) differentially bind to various RAREs in proximal promoters or enhancer regions of RA-regulated genes; HDAC1, HDAC2, and HDAC3 bind at RAREs in the Hoxa1 and Cyp26a1 gene regulatory regions, whereas only HDAC1 binds at the RARβ2 RARE. shRNA knockdown of HDAC1, HDAC2, or HDAC3 differentially increases the deposition of the histone 3 lysine 27 acetylation (H3K27ac) epigenetic mark associated with increases in these three transcripts. Importantly, RA treatment differentially mediates the removal of HDACs from the Hoxa1, Cyp26a1, and RARβ2 genes and promotes the deposition of the H3K27ac mark at these genes. Overall, we show that HDACs differentially bind to RA-regulated genes to control key epigenetic marks involved in stem cell differentiation.