Embryonic stem (ES) cell self-renewal efficiency is determined by the Nanog protein level. However, the protein partners of Nanog that function to direct self-renewal are unclear. Here, we identify a Nanog interactome of over 130 proteins including transcription factors, chromatin modifying complexes, phosphorylation and ubiquitination enzymes, basal transcriptional machinery members, and RNA processing factors. Sox2 was identified as a robust interacting partner of Nanog. The purified Nanog–Sox2 complex identified a DNA recognition sequence present in multiple overlapping Nanog/Sox2 ChIP-Seq data sets. The Nanog tryptophan repeat region is necessary and sufficient for interaction with Sox2, with tryptophan residues required. In Sox2, tyrosine to alanine mutations within a triple-repeat motif (S X T/S Y) abrogates the Nanog–Sox2 interaction, alters expression of genes associated with the Nanog-Sox2 cognate sequence, and reduces the ability of Sox2 to rescue ES cell differentiation induced by endogenous Sox2 deletion. Substitution of the tyrosines with phenylalanine rescues both the Sox2–Nanog interaction and efficient self-renewal. These results suggest that aromatic stacking of Nanog tryptophans and Sox2 tyrosines mediates an interaction central to ES cell self-renewal.