Melanoma cells share many biological properties with neural crest stem cells. Here we show that the homeodomain transcription factor Msh homeobox 1 (MSX1), which is significantly correlated with melanoma disease progression, reprograms melanocytes and melanoma cells towards a neural crest precursor-like state. MSX1-reprogrammed normal human melanocytes express the neural crest marker p75 and become multipotent. MSX1 induces a phenotypic switch in melanoma, which is characterized by an oncogenic transition from an E-cadherin-high non-migratory state towards a ZEB1-high invasive state. ZEB1 up-regulation is responsible for the MSX1-induced migratory phenotype in melanoma cells. Depletion of MSX1 significantly inhibits melanoma metastasis in vivo. These results demonstrate that neural crest-like reprogramming achieved by a single factor is a critical process for melanoma progression.