NF1-associated malignant peripheral nerve sheath tumors (MPNSTs) are the major cause of mortality in neurofibromatosis. MPNSTs arise from benign peripheral nerve plexiform neurofibromas that originate in the embryonic neural crest cell lineage. Using reporter transgenes that label early neural crest lineage cells in multiple NF1 MPNST mouse models, we discover and characterize a rare MPNST cell population with stem-cell-like properties, including quiescence, that is essential for tumor initiation and relapse. Following isolation of these cells, we derive a cancer-stem-cell-specific gene expression signature that includes consensus embryonic neural crest genes and identify Nestin as a marker for the MPNST cell of origin. Combined targeting of cancer stem cells along with antimitotic chemotherapy yields effective tumor inhibition and prolongs survival. Enrichment of the cancer stem cell signature in cognate human tumors supports the generality and relevance of cancer stem cells to MPNST therapy development.