The Polycomb group (PcG) proteins form chromatin-modifying complexes that are essential for embryonic development and stem cell renewal and are commonly deregulated in cancer. Here, we identify their target genes using genome-wide location analysis in human embryonic fibroblasts. We find that Polycomb-Repressive Complex 1 (PRC1), PRC2, and tri-methylated histone H3K27 co-occupy >1000 silenced genes with a strong functional bias for embryonic development and cell fate decisions. We functionally identify 40 genes derepressed in human embryonic fibroblasts depleted of the PRC2 components (EZH2, EED, SUZ12) and the PRC1 component, BMI-1. Interestingly, several markers of osteogenesis, adipogenesis, and chrondrogenesis are among these genes, consistent with the mesenchymal origin of fibroblasts. Using a neuronal model of differentiation, we delineate two different mechanisms for regulating PcG target genes. For genes activated during differentiation, PcGs are displaced. However, for genes repressed during differentiation, we paradoxically find that they are already bound by the PcGs in nondifferentiated cells despite being actively transcribed. Our results are consistent with the hypothesis that PcGs are part of a preprogrammed memory system established during embryogenesis marking certain key genes for repressive signals during subsequent developmental and differentiation processes.