Epigenetic modifications such as histone methylation play an important role in human cancer metastasis. Enhancer of zeste homolog 2 (EZH2), which encodes the histone methyltransferase component of the polycomb repressive complex 2 (PRC2), is overexpressed widely in breast and prostate cancers and epigenetically silences tumor suppressor genes. Expression levels of the novel tumor and metastasis suppressor Raf-1 kinase inhibitor protein (RKIP) have been shown to correlate negatively with those of EZH2 in breast and prostate cell lines as well as in clinical cancer tissues. Here, we show that the RKIP/EZH2 ratio significantly decreases with the severity of disease and is negatively associated with relapse-free survival in breast cancer. Using a combination of loss- and gain-of-function approaches, we found that EZH2 negatively regulated RKIP transcription through repression-associated histone modifications. Direct recruitment of EZH2 and suppressor of zeste 12 (Suz12) to the proximal E-boxes of the RKIP promoter was accompanied by H3-K27-me3 and H3-K9-me3 modifications. The repressing activity of EZH2 on RKIP expression was dependent on histone deacetylase promoter recruitment and was negatively regulated upstream by miR-101. Together, our findings indicate that EZH2 accelerates cancer cell invasion, in part, via RKIP inhibition. These data also implicate EZH2 in the regulation of RKIP transcription, suggesting a potential mechanism by which EZH2 promotes tumor progression and metastasis.