Ineffective hematopoiesis is a major characteristic of myelodysplastic syndromes (MDS) causing relevant morbidity and mortality. Mesenchymal stromal cells (MSC) have been shown to physiologically support hematopoiesis, but their contribution to the pathogenesis of MDS remains elusive. We show that MSC from patients across all MDS subtypes (n = 106) exhibit significantly reduced growth and proliferative capacities accompanied by premature replicative senescence. Osteogenic differentiation was significantly reduced in MDS-derived MSC, indicated by cytochemical stainings and reduced expressions of Osterix and Osteocalcin. This was associated with specific methylation patterns that clearly separated MDS-MSC from healthy controls and showed a strong enrichment for biological processes associated with cellular phenotypes and transcriptional regulation. Furthermore, in MDS-MSC, we detected altered expression of key molecules involved in the interaction with hematopoietic stem and progenitor cells (HSPC), in particular Osteopontin, Jagged1, Kit-ligand and Angiopoietin as well as several chemokines. Functionally, this translated into a significantly diminished ability of MDS-derived MSC to support CD34+ HSPC in long-term culture-initiating cell assays associated with a reduced cell cycle activity. Taken together, our comprehensive analysis shows that MSC from all MDS subtypes are structurally, epigenetically and functionally altered, which leads to impaired stromal support and seems to contribute to deficient hematopoiesis in MDS.