Nearly all CpG-dense promoters are occupied by the multidomain chromosomal protein FBXL10. We show here that complete inactivation of the Fbxl10 gene leads to dense de novo methylation only of promoters that are co-occupied by both FBXL10 and Polycomb repressive complexes; this methylation results in pervasive defects in embryonic development and the death of homozygous Fbxl10-mutant embryos at midgestation. Deletion of key components of Polycomb repressive complexes 1 and 2 did not lead to ectopic genomic methylation. These results indicate that FBXL10 protects Polycomb-occupied promoters against ectopic de novo methylation. To our knowledge, FBXL10 is the first reported factor whose loss leads to a gain in genomic DNA methylation.