Epigenetic memory mediated by Polycomb group (PcG) proteins must be maintained during cell division, but must also be flexible to allow cell fate transitions. Here we quantify dynamic chromatin-binding properties of PH::GFP and PC::GFP in living Drosophila in two cell types that undergo defined differentiation and mitosis events. Quantitative fluorescence recovery after photobleaching (FRAP) analysis demonstrates that PcG binding has a higher plasticity in stem cells than in more determined cells and identifies a fraction of PcG proteins that binds mitotic chromatin with up to 300-fold longer residence times than in interphase. Mathematical modeling examines which parameters best distinguish stem cells from differentiated cells. We identify phosphorylation of histone H3 at Ser 28 as a potential mechanism governing the extent and rate of mitotic PC dissociation in different lineages. We propose that regulation of the kinetic properties of PcG-chromatin binding is an essential factor in the choice between stability and flexibility in the establishment of cell identities.