Despite advances in therapeutics, the progression of melanoma to metastasis still confers a poor outcome to patients. Nevertheless, there is a scarcity of biological models to understand cellular and molecular changes taking place along disease progression. Here, we characterized the transcriptome profiles of a multi-stage murine model of melanoma progression comprising a nontumorigenic melanocyte lineage (melan-a), premalignant melanocytes (4C), nonmetastatic (4C11-) and metastasis-prone (4C11+) melanoma cells. Clustering analyses have grouped the 4 cell lines according to their differentiated (melan-a and 4C11+) or undifferentiated/“mesenchymal-like” (4C and 4C11-) morphologies, suggesting dynamic gene expression patterns associated with the transition between these phenotypes. The cell plasticity observed in the murine melanoma progression model was corroborated by molecular markers described during stepwise human melanoma differentiation, as the differentiated cell lines in our model exhibit upregulation of transitory and melanocytic markers, whereas “mesenchymal-like” cells show increased expression of undifferentiated and neural crest-like markers. Sets of differentially expressed genes (DEGs) were detected at each transition step of tumor progression, and transcriptional signatures related to malignancy, metastasis and epithelial-to-mesenchymal transition were identified. Finally, DEGs were mapped to their human orthologs and evaluated in uni- and multivariate survival analyses using gene expression and clinical data of 703 drug-naïve primary melanoma patients, revealing several independent candidate prognostic markers. Altogether, these results provide novel insights into the molecular mechanisms underlying the phenotypic switch taking place during melanoma progression, reveal potential drug targets and prognostic biomarkers, and corroborate the translational relevance of this unique sequential model of melanoma progression.