Cutaneous melanoma represents one of the deadliest types of skin cancer. The prognosis strongly depends on the disease stage, thus early detection is crucial. New therapies, including BRAF and MEK inhibitors and immunotherapies, have significantly improved the survival of patients in the last decade. However, intrinsic and acquired resistance is still a challenge. In this review, we discuss two major aspects that contribute to the aggressiveness of melanoma, namely, the embryonic origin of melanocytes and melanoma cells and cellular plasticity. First, we summarize the physiological function of epidermal melanocytes and their development from precursor cells that originate from the neural crest (NC). Next, we discuss the concepts of intratumoral heterogeneity, cellular plasticity, and phenotype switching that enable melanoma to adapt to changes in the tumor microenvironment and promote disease progression and drug resistance. Finally, we further dissect the connection of these two aspects by focusing on the transcriptional regulators MSX1, MITF, SOX10, PAX3, and FOXD3. These factors play a key role in NC initiation, NC cell migration, and melanocyte formation, and we discuss how they contribute to cellular plasticity and drug resistance in melanoma.