Molecular control of the pluripotent state is thought to reside in a core circuitry of master transcription factors including the homeodomain-containing protein NANOG, which has an essential role in establishing ground state pluripotency during somatic cell reprogramming. Whereas the genomic occupancy of NANOG has been extensively investigated, comparatively little is known about NANOG-associated proteins and their contribution to the NANOG-mediated reprogramming process. Using enhanced purification techniques and a stringent computational algorithm, we identify 27 high-confidence protein interaction partners of NANOG in mouse embryonic stem cells. These consist of 19 previously unknown partners of NANOG that have not been reported before, including the ten-eleven translocation (TET) family methylcytosine hydroxylase TET1. We confirm physical association of NANOG with TET1, and demonstrate that TET1, in synergy with NANOG, enhances the efficiency of reprogramming. We also find physical association and reprogramming synergy of TET2 with NANOG, and demonstrate that knockdown of TET2 abolishes the reprogramming synergy of NANOG with a catalytically deficient mutant of TET1. These results indicate that the physical interaction between NANOG and TET1/TET2 proteins facilitates reprogramming in a manner that is dependent on the catalytic activity of TET1/TET2. TET1 and NANOG co-occupy genomic loci of genes associated with both maintenance of pluripotency and lineage commitment in embryonic stem cells, and TET1 binding is reduced upon NANOG depletion. Co-expression of NANOG and TET1 increases 5-hydroxymethylcytosine levels at the top-ranked common target loci Esrrb and Oct4 (also called Pou5f1), resulting in priming of their expression before reprogramming to naive pluripotency. We propose that TET1 is recruited by NANOG to enhance the expression of a subset of key reprogramming target genes. These results provide an insight into the reprogramming mechanism of NANOG and uncover a new role for 5-methylcytosine hydroxylases in the establishment of naive pluripotency.