During embryonic development, maintenance of cell identity and lineage commitment requires the Polycomb-group PRC2 complex, which catalyzes histone H3 lysine 27 trimethylation (H3K27me3). However, the developmental origins of this regulation are unknown. Here we show that H3K27me3 enrichment increases from blastula stages onward in embryos of the Western clawed frog (Xenopus tropicalis) within constrained domains strictly defined by sequence. Strikingly, although PRC2 also binds widely to active enhancers, H3K27me3 is only deposited at a small subset of these sites. Using a Support Vector Machine algorithm, these sequences can be predicted accurately on the basis of DNA sequence alone, with a sequence signature conserved between humans, frogs, and fish. These regions correspond to the subset of blastula-stage DNA methylation-free domains that are depleted for activating promoter motifs, and enriched for motifs of developmental factors. These results imply a genetic-default model in which a preexisting absence of DNA methylation is the major determinant of H3K27 methylation when not opposed by transcriptional activation. The sequence and motif signatures reveal the hierarchical and genetically inheritable features of epigenetic cross-talk that impose constraints on Polycomb regulation and guide H3K27 methylation during the exit of pluripotency.