Melanoma cells are notorious for their high plasticity and ability to switch back and forth between various melanoma cell states, enabling the adaptation to sub-optimal conditions and therapeutics. This phenotypic plasticity, which has gained more attention in cancer research, is proposed as a new paradigm for melanoma progression. In this review, we provide a detailed and deep comprehensive recapitulation of the complex spectrum of phenotype switching in melanoma, the key regulator factors, the various and new melanoma states, and corresponding signatures. We also present an extensive description of the role of epigenetic modifications (chromatin remodeling, methylation, and activities of long non-coding RNAs/miRNAs) and metabolic rewiring in the dynamic switch. Furthermore, we elucidate the main role of the crosstalk between the tumor microenvironment (TME) and oxidative stress in the regulation of the phenotype switching. Finally, we discuss in detail several rational therapeutic approaches, such as exploiting phenotype-specific and metabolic vulnerabilities and targeting components and signals of the TME, to improve the response of melanoma patients to treatments.