Histone deacetylase 3 (HDAC3) is one of four members of the human class I HDACs that regulates gene expression by deacetylation of histones and nonhistone proteins. Early studies have suggested that HDAC3 activity is regulated by association with the corepressors N-CoR and SMRT. Here we demonstrate that, in addition to protein-protein interactions with NCoR/SMRT, the activity of HDAC3 is regulated by both phosphorylation and dephosphorylation. A protein kinase CK2 phosphoacceptor site in the HDAC3 protein was identified at position Ser424, which is a nonconserved residue among the class I HDACs. Mutation of this residue was found to reduce deacetylase activity. Interestingly, unlike other class I HDACs, HDAC3 uniquely copurifies with the catalytic and regulatory subunits of the protein serine/threonine phosphatase 4 complex (PP4c/PP4R1). Furthermore, HDAC3 complexes displayed protein phosphatase activity and a series of subsequent mutational analyses revealed that the N terminus of HDAC3 (residues 1-122) was both necessary and sufficient for HDAC3-PP4c interactions. Significantly, both overexpression and siRNA knock-down approaches, and analysis of cells devoid of PP4c, unequivocally show that HDAC3 activity is inversely proportional to the cellular abundance of PP4(c). These findings therefore further highlight the importance of protein-protein interactions and extend the significance of dephosphorylation in the regulation of HDAC activity, as well as present a novel alternative pathway by which HDAC3 activity is regulated.