Functional telomeres are critical for stem cell proliferation; however, whether they are equally important for the stability of stem cell differentiation is not known. We found that mouse embryonic stem cells (ESCs) with critically short telomeres (Tert(-/-) ESCs) initiated normal differentiation after leukemia inhibitory factor (LIF) withdrawal but, unlike control ESCs, failed to maintain stable differentiation when LIF was reintroduced to the growth medium. Tert(-/-) ESCs expressed higher levels of Nanog and, overall, had decreased genomic CpG methylation levels, which included the promoters of Oct4 and Nanog. This unstable differentiation phenotype could be rescued by telomere elongation via reintroduction of Tert, via suppression of Nanog by small hairpin RNA (shRNA) knockdown, or via enforced expression of the de novo DNA methyltransferase 3b. These results demonstrate an unexpected role of functional telomeres in the genome-wide epigenetic regulation of cell differentiation and suggest a potentially important role of telomere instability in cell fate during development or disease.