Cutaneous malignant melanomas share a number of molecular attributes such as limitless replicative potential that define capabilities acquired by most malignancies. Accordingly, much effort has been focused on evaluating and validating protein markers related to these capabilities to function as melanoma prognostic markers. However, a few studies have also highlighted the prognostic value of markers that define melanocytic differentiation and the plasticity of melanoma cells to trans-differentiate along several other cellular pathways. Here, we provide a comprehensive review and evaluation of the prognostic significance of melanocyte-lineage markers such as MITF and melanogenic proteins, as well as markers of vascular epithelial and neuronal differentiation.