The bone marrow microenvironment is composed of heterogeneous cell populations of non-hematopoietic cells with complex phenotypes and undefined trajectories of maturation. Among them, mesenchymal cells maintain the production of stromal, bone, fat, and cartilage cells. Resolving these unique cellular subsets within the bone marrow remains challenging. Here, we used single-cell RNA sequencing of non-hematopoietic bone marrow cells to define specific subpopulations. Furthermore, by combining computational prediction of the cell state hierarchy with the known expression of key transcription factors, we mapped differentiation paths to the osteocyte, chondrocyte, and adipocyte lineages. Finally, we validated our findings using lineage-specific reporter strains and targeted knockdowns. Our analysis reveals differentiation hierarchies for maturing stromal cells, determines key transcription factors along these trajectories, and provides an understanding of the complexity of the bone marrow microenvironment. Using single-cell RNA sequencing, Wolock et al. reconstruct the transcriptional hierarchy of mouse bone marrow stromal cell states and infer differentiation paths to fat, bone, and cartilage. These cell state relations were validated using lineage-specific reporter strains and targeted knockdowns of transcription factors that mediate fate decisions.