The cis-trans isomerization of proline serves as a regulatory switch in signaling pathways. We identify the proline isomerase Fpr4, a member of the FK506 binding protein family in Saccharomyces cerevisiae, as an enzyme which binds the amino-terminal tail of histones H3 and H4 and catalyses the isomerization of H3 proline P30 and P38 in vitro. We show that P38 is necessary for methylation of K36 and that isomerization by Fpr4 inhibits the ability of Set2 to methylate H3 K36 in vitro. These results suggest that the conformational state of P38, controlled by Fpr4, is important for methylation of H3K36 by Set2. Consistent with such an antagonistic role, abrogation of Fpr4 catalytic activity in vivo results in increased levels of H3K36 methylation and delayed transcriptional induction kinetics of specific genes in yeast. These results identify proline isomerization as a novel noncovalent histone modification that regulates transcription and provides evidence for crosstalk between histone lysine methylation and proline isomerization.