Transcription factors that play key roles in regulating embryonic stem (ES) cell state have been identified, but the chromatin regulators that help maintain ES cells are less well understood. A high-throughput shRNA screen was used to identify novel chromatin regulators that influence ES cell state. Loss of histone H3 Lys 9 (H3K9) methyltransferases, particularly SetDB1, had the most profound effects on ES cells. Chromatin immunoprecipitation (ChIP) coupled with massively parallel DNA sequencing (ChIP-Seq) and functional analysis revealed that SetDB1 and histone H3K9-methylated nucleosomes occupy and repress genes encoding developmental regulators. These SetDB1-occupied genes are a subset of the "bivalent" genes, which contain nucleosomes with H3K4me3 (H3K4 trimethylation) and H3K27me3 modifications catalyzed by Trithorax and Polycomb group proteins, respectively. These genes are subjected to repression by both Polycomb group proteins and SetDB1, and loss of either regulator can destabilize ES cell state.