This study investigates the mechanism by which histone deacetylase (HDAC) inhibitors up-regulate histone H3 lysine 4 (H3K4) methylation. Exposure of LNCaP prostate cancer cells and the prostate tissue of transgenic adenocarcinoma of the mouse prostate mice to the pan- and class I HDAC inhibitors (S)-(+)-N-hydroxy-4-(3-methyl-2-phenyl-butyrylamino)-benzamide (AR42), N-(2-aminophenyl)-4-[N-(pyridine-3-yl-methoxycarbonyl)-aminomethyl]-benzamide (MS-275), and vorinostat led to differential increases in H3K4 methylation. Chromatin immunoprecipitation shows that this accumulation of methylated H3K4 occurred in conjunction with decreases in the amount of the H3K4 demethylase RBP2 at the promoter of genes associated with tumor suppression and differentiation, including KLF4 and E-cadherin. This finding, together with the HDAC inhibitor-induced up-regulation of KLF4 and E-cadherin, suggests that HDAC inhibitors could activate the expression of these genes through changes in histone methylation status. Evidence indicates that this up-regulation of H3K4 methylation was attributable to the suppressive effect of these HDAC inhibitors on the expression of RBP2 and other JARID1 family histone demethylases, including PLU-1, SMCX, and LSD1, via the down-regulation of Sp1 expression. Moreover, shRNA-mediated silencing of the class I HDAC isozymes 1, 2, 3, and 8, but not that of the class II isozyme HDAC6, mimicked the drug effects on H3K4 methylation and H3K4 demethylases, which could be reversed by ectopic Sp1 expression. These data suggest a cross-talk mechanism between HDACs and H3K4 demethylases via Sp1-mediated transcriptional regulation, which underlies the complexity of the functional role of HDACs in the regulation of histone modifications.