The chromatin-associated Polycomb Group (PcG) proteins were first identified in genetic screens for homeotic transformations in Drosophila melanogaster. In addition to body patterning in metazoans, members of the PcG are now known to regulate epigenetic cellular memory, pluripotency and stem cell self-renewal. Here, we discuss the functional versatility of the PcG family and the evolutionary history of a subset of these proteins including Drosophila E(z), Pc, Psc, dRing and their homologs in plants and animals. We propose that PcG gene expansion and diversification contributed significantly to the complexity of heritable gene repression mechanisms in extant multicellular organisms.