Polycomb group genes were identified as a conserved group of genes whose products are required in multimeric complexes to maintain spatially restricted expression of Hox cluster genes. Unlike in Drosophila, in mammals Polycomb group (PcG) genes are represented as highly related gene pairs, indicative of duplication during metazoan evolution. Mel18 and Bmi1 are mammalian homologs of Drosophila Posterior sex combs. Mice deficient for Mel18 or Bmi1 exhibit similar posterior transformations of the axial skeleton and display severe immune deficiency, suggesting that their gene products act on overlapping pathways/target genes. However unique phenotypes upon loss of either Mel18 or Bmi1 are also observed. We show using embryos doubly deficient for Mel18 and Bmi1 that Mel18 and Bmi1 act in synergy and in a dose-dependent and cell type-specific manner to repress Hox cluster genes and mediate cell survival of embryos during development. In addition, we demonstrate that Mel18 and Bmi1, although essential for maintenance of the appropriate expression domains of Hox cluster genes, are not required for the initial establishment of Hox gene expression. Furthermore, we show an unexpected requirement for Mel18 and Bmi1 gene products to maintain stable expression of Hox cluster genes in regions caudal to the prospective anterior expression boundaries during subsequent development.