Telomere length (TL) and telomere shortening are biological indicators of aging, and epigenetic associates have been found for TL in adults. However, the role of epigenetic signatures in setting newborn TL and early life telomere dynamics is unknown. In the present study, based on 247 participating newborns from the ENVIRONAGE birth cohort, whole-genome DNA methylation, profiled on the Illumina MethylationEPIC BeadChip microarray, and TL were measured in cord blood. In a follow-up visit at a mean age of 4.58 years, leukocyte TL was evaluated. We combined an epigenome-wide association study and a statistical learning method with re-sampling to select CpGs and their two-way interactions to model baseline (cord blood) TL and early-life telomere attrition rate, where distinct epigenetic signatures were identified for the two outcomes. In addition, a stronger epigenetic regulation was suggested in setting newborn TL than that of telomere dynamics in early life: 47 CpGs and 7 between-CpG interactions explained 76% of the variance in baseline TLs, while 72% of the total variance in telomere attrition rate was explained by 31 CpGs and 5 interactions. Functional enrichment analysis based on the selected CpGs in the two models revealed GLUT4 translocation and immune cell signaling pathways, respectively. These CpGs and interactions, as well as the cellular pathways, are potential novel targets of further investigation of telomere biology and aging.