We demonstrate that subpopulations of adult human skeletal muscle-derived stem cells, myogenic endothelial cells (MECs), and perivascular stem cells (PSCs) can be simultaneously purified by fluorescence-activated cell sorting (FACS) from cryopreserved human primary skeletal muscle cell cultures (cryo-hPSMCs). For FACS isolation, we utilized a combination of cell lineage markers: the myogenic cell marker CD56, the endothelial cell marker UEA-1 receptor (UEA-1R), and the perivascular cell marker CD146. MECs expressing all three cell lineage markers (CD56(+)UEA-1R(+)CD146(+)/CD45(-)) and PSCs expressing only CD146 (CD146(+)/CD45(-)CD56(-)UEA-1R(-)) were isolated by FACS. To evaluate their myogenic capacities, the sorted cells, with and without expansion in culture, were transplanted into the cardiotoxin-injured skeletal muscles of immunodeficient mice. The purified MECs exhibited the highest regenerative capacity in the injured mouse muscles among all cell fractions tested, while PSCs remained superior to myoblasts and the unpurified primary skeletal muscle cells. Our findings show that both MECs and PSCs retain their high myogenic potentials after in vitro expansion, cryopreservation, and FACS sorting. The current study demonstrates that myogenic stem cells are prospectively isolatable from long-term cryopreserved primary skeletal muscle cell cultures. We emphasize the potential application of this new approach to extract therapeutic stem cells from human muscle cells cryogenically banked for clinical purposes.