Polycomb- (PcG) and trithorax (trxG) group proteins are essential components in the regulation of multiple developmental regulators. In particular, during early stages, they act as chromatin modifiers in such a way as to set and maintain the transcriptional status of Hox genes. Little is known, in vertebrates, concerning the modalities of PcG binding to their target sites. One possibility is that they are recruited, in a synergistic manner, through their binding to specific DNA regulatory elements to control spatial and temporal restriction of Hox genes by trimethylating lysine 27 on histone 3 (H3K27me3). Whereas these DNA sequences, referred to as polycomb response elements (PREs), have been identified in Drosophila, their existence in mammals remains to be clearly demonstrated. In this work, we aim to decipher the means by which polycomb repressive complexes (PRCs) are recruited to PREs during early mouse development and focus on the HoxD cluster, a genomic segment that is amongst the most heavily covered by H3K27me3 marks in embryonic stem (ES) cells and where one of the few vertebrate PRE has been previously reporter. We describe relatively small DNA sequences lying within the HoxD locus that are necessary and sufficient for the tethering of polycomb to ectopic loci. These elements work synergistically to form a fully functional repressive domain. Moreover, we show that a sequence with high GC content, although not necessary for the initial recruitment of PRC per se, may stabilize the link between the complex and the underlying DNA. Finally, we propose a model for the evolution of polycomb targets and discuss the emergence of diverging recruitment mechanisms amongst Drosophila, mice and humans.