Early social deprivation (i.e., an insufficiency or lack of parental care) has been identified as a significant adverse early experience that may affect multiple facets of child development and cause long-term outcomes in physical and mental health, cognition and behavior. Current research provides growing evidence that epigenetic reprogramming may be a mechanism modulating these effects of early adversities. This work aimed to investigate the impact of early institutionalization—the immersion in an extreme socially depriving environment in humans—on the epigenome and adaptive behavior of young children up to 4 years of age. We conducted a cross-sectional study involving two comparison groups: 29 children raised in orphanages and 29 children raised in biological families. Genome-wide DNA methylation profiles of blood cells were obtained using the Illumina MethylationEPIC array; the level of child adaptive functioning was assessed using the Vineland Adaptive Behavior Scales-II. In comparison to children raised in families, children residing in orphanages had both statistically significant deficits in multiple adaptive behavior domains and statistically significant differences in DNA methylation states. Moreover, some of these methylation states may directly modulate the behavioral deficits; according to preliminary estimates, about 7–14% of the deviation of adaptive behavior between groups of children may be determined by their difference in DNA methylation profiles. The duration of institutionalization had a significant impact on both the adaptive level and DNA methylation status of institutionalized children.