FK506-binding proteins (FKBPs) are cellular receptors for immunosuppressants that belong to a subgroup of proteins, known as immunophilins, with peptidylprolyl cis–trans isomerase (PPIase) activity. Sequence comparison suggested that the HD2-type histone deacetylases and the FKBP-type PPIases may have evolved from a common ancestor enzyme. Here we show that FKBP25 physically associates with the histone deacetylases HDAC1 and HDAC2 and with the HDAC-binding transcriptional regulator YY1. An FKBP25 immunoprecipitated complex contains deacetylase activity, and this activity is associated with the N-terminus of FKBP25, distinct from the FK506/rapamycin-binding domain. Furthermore, FKBP25 can alter the DNA-binding activity of YY1. Together, our data firmly establish a relationship between histone deacetylases and the FKBP enzymes and provide a novel and critical function for the FKBPs.