Tumors evolve from initial tumorigenic events into increasingly aggressive behaviors in a process usually driven by subpopulations of cancer stem cells (CSCs). Mesenchymal stromal/stem cells (MSCs) may act as the cell-of-origin for sarcomas, and CSCs that present MSC features have been identified in sarcomas due to their ability to grow as self-renewed floating spheres (tumorspheres). Accordingly, we previously developed sarcoma models using human MSCs transformed with relevant oncogenic events. To study the evolution/emergence of CSC subpopulations during tumor progression, we compared the tumorigenic properties of bulk adherent cultures and tumorsphere-forming subpopulations both in the sarcoma cell-of-origin models (transformed MSCs) and in their corresponding tumor xenograft-derived cells. Tumor formation assays showed that the tumorsphere cultures from xenograft-derived cells, but not from the cell-of-origin models, were enriched in CSCs, providing evidence of the emergence of bona fide CSCs subpopulations during tumor progression. Relevant CSC-related factors, such as ALDH1 and SOX2, were increasingly upregulated in CSCs during tumor progression, and importantly, the increased levels and activity of ALDH1 in these subpopulations were associated with enhanced tumorigenicity. In addition to being a CSC marker, our findings indicate that ALDH1 could also be useful for tracking the malignant potential of CSC subpopulations during sarcoma evolution.