Transcription factors (TF) often bind in heterodimeric complexes with each TF recognizing a specific neighboring cis element in the regulatory region of the genome. Comprehension of this DNA motif grammar is opaque, yet recent developments have allowed the interrogation of genome-wide TF binding sites. We reasoned that within this data novel motif grammars could be identified that controlled distinct biological programs. For this purpose, we developed a novel motif-discovery tool termed fexcom that systematically interrogates ChIP-seq data to discover spatially constrained TF–TF composite motifs occurring over short DNA distances. We applied this to the extensive ChIP-seq data available from mouse embryonic stem cells (ESCs). In addition to the well-known and most prevalent sox-oct motif, we also discovered a novel constrained spacer motif for Esrrb and Sox2 with a gap of between 2 and 8 bps that Essrb and Sox2 cobind in a selective fashion. Through the use of knockdown experiments, we argue that the Esrrb-Sox2 complex is an arbiter of gene expression differences between ESCs and epiblast stem cells (EpiSC). A number of genes downregulated upon dual Esrrb/Sox2 knockdown (e.g., Klf4, Klf5, Jam2, Pecam1) are similarly downregulated in the ESC to EpiSC transition and contain the esrrb-sox motif. The prototypical Esrrb-Sox2 target gene, containing an esrrb-sox element conserved throughout eutherian and metatherian mammals, is Nr0b1. Through positive regulation of this transcriptional repressor, we argue the Esrrb-Sox2 complex promotes the ESC state through inhibition of the EpiSC transcriptional program and the same trio may also function to maintain trophoblast stem cells.