Nanog and Oct4 are essential transcription factors that regulate self-renewal and pluripotency of ES cells. However, the mechanisms by which Nanog and Oct4 modulate ES cell fate remain unknown. Through characterization of endogenous Nanog and Oct4 protein complexes in mouse ES cells, we found that these transcription factors interact with each other and associate with proteins from multiple repression complexes, including the NuRD, Sin3A and Pml complexes. In addition, Nanog, Oct4 and repressor proteins co-occupy Nanog-target genes in mouse ES cells, suggesting that Nanog and Oct4 together may communicate with distinct repression complexes to control gene transcription. To our surprise, of the various core components in the NuRD complex with which Nanog and Oct4 interact, Mta1 was preferred, whereas Mbd3 and Rbbp7 were either absent or present at sub-stoichiometric levels. We named this unique Hdac1/2- and Mta1/2-containing complex NODE (for Nanog and Oct4 associated deacetylase). Interestingly, NODE contained histone deacetylase (HDAC) activity that seemed to be comparable to NuRD, and retained its association with Nanog and Oct4 in Mbd3(-/-) ES cells. In contrast to Mbd3 loss-of-function, knockdown of NODE subunits led to increased expression of developmentally regulated genes and ES-cell differentiation. Our data collectively suggest that Nanog and Oct4 associate with unique repressor complexes on their target genes to control ES cell fate.