Mesenchymal stem cells (MSCs) isolated from various tissues share common phenotypic and functional properties. However, intrinsic molecular evidence supporting these observations has been lacking. Here, we unravel overlapping genome-wide promoter DNA methylation patterns between MSCs from adipose tissue, bone marrow, and skeletal muscle, whereas hematopoietic progenitors are more epigenetically distant from MSCs as a whole. Commonly hypermethylated genes are enriched in signaling, metabolic, and developmental functions, whereas genes hypermethylated only in MSCs are associated with early development functions. We find that most lineage-specification promoters are DNA hypomethylated and harbor a combination of trimethylated H3K4 and H3K27, whereas early developmental genes are DNA hypermethylated with or without H3K27 methylation. Promoter DNA methylation patterns of differentiated cells are largely established at the progenitor stage; yet, differentiation segregates a minor fraction of the commonly hypermethylated promoters, generating greater epigenetic divergence between differentiated cell types than between their undifferentiated counterparts. We also show an effect of promoter CpG content on methylation dynamics upon differentiation and distinct methylation profiles on transcriptionally active and inactive promoters. We infer that methylation state of lineage-specific promoters in MSCs is not a primary determinant of differentiation capacity. Our results support the view of a common origin of mesenchymal progenitors.