The Polycomb group of proteins (PcG) maintains stable epigenetic silencing of over 100 genes via PcG response elements (PREs). Here we investigate the relationship between Polycomb binding, transcriptional status, and histone H3 methylation at lysine 9 (H3K9Me) and 27 (H3K27Me) for over 30 PcG targets in Drosophila. We show that H3K9Me and H3K27Me have distinct distributions at different loci. Our data show that Polycomb binding and histone methylation at the promoter do not prevent strong transcriptional activity, and indicate instead that silencing requires methylation of both PRE and promoter. In addition, we show that trimethylated H3K9 and H3K27 peptides can compete Polycomb from polytene chromosomes, with different effects at different loci, which correlate with differences in methylation status and transcriptional activity. We use mathematical modeling to examine these data, and propose that weak Polycomb-histone tail interactions enable PcG complexes to bind dynamically to chromatin, offering opportunities for regulation.