Polycomb group (PcG) proteins are important epigenetic regulatory proteins that modulate the chromatin state through posttranslational histone modifications. These interacting proteins form multimeric complexes that repress gene expression. Thus, PcG proteins are expected to evolve coordinately, which might be reflected in their phylogenetic trees by concordant episodes of positive selection and by a correlation in evolutionary rates. In order to detect these signals of coevolution, the molecular evolution of 17 genes encoding the subunits of five Polycomb repressive complexes has been analyzed in the Drosophila genus. The observed distribution of divergence differs substantially among and along proteins. Indeed, CAF1 is uniformly conserved, whereas only the established protein domains are conserved in other proteins, such as PHO, PHOL, PSC, PH-P and ASX. Moreover, regions with a low divergence not yet described as protein domains are present, for instance, in SFMBT and SU(Z)12. Maximum likelihood methods indicate an acceleration in the nonsynonymous substitution rate at the lineage ancestral to the obscura group species in most genes encoding subunits of the Pcl-PRC2 complex and in genes Sfmbt, Psc and Kdm2. These methods also allow inferring the action of positive selection in this lineage at genes E(z) and Sfmbt. Finally, the protein interaction network predicted from the complete proteomes of 12 Drosophila species using a coevolutionary approach shows two tight PcG clusters. These clusters include well-established binary interactions among PcG proteins as well as new putative interactions.