The Polycomb group (PcG) protein Eed is implicated in regulation of imprinted X-chromosome inactivation in extraembryonic cells but not of random X inactivation in embryonic cells. The Drosophila homolog of the Eed-Ezh2 PcG protein complex achieves gene silencing through methylation of histone H3 on lysine 27 (H3-K27), which suggests a role for H3-K27 methylation in imprinted X inactivation. Here we demonstrate that transient recruitment of the Eed-Ezh2 complex to the inactive X chromosome (Xi) occurs during initiation of X inactivation in both extraembryonic and embryonic cells and is accompanied by H3-K27 methylation. Recruitment of the complex and methylation on the Xi depend on Xist RNA but are independent of its silencing function. Together, our results suggest a role for Eed-Ezh2-mediated H3-K27 methylation during initiation of both imprinted and random X inactivation and demonstrate that H3-K27 methylation is not sufficient for silencing of the Xi.