Cutaneous malignant melanoma remains the leading cause of skin cancer death in industrialized countries. Clinical and histological variables that predict survival, such as Breslow's index, tumor size, ulceration, or vascular invasion have been identified in malignant melanoma. Nevertheless, the potential relevance of biological variables still awaits an in-depth exploration. Using tissue microarrays (TMAs), we retrospectively analyzed 165 malignant melanoma samples from 88 patients corresponding to distinct histological progression phases, radial, vertical, and metastases. A panel of 39 different antibodies for cell cycle, apoptosis, melanoma antigens, transcription factors, DNA mismatch repair, and other proteins was used. Integrating the information, the study has identified expression profiles distinguishing specific melanoma progression stages. Most of the detected alterations were linked to the control of cell cycle G1/S transition; cyclin D1 was expressed in radial cases 48% (12 of 25) with significant lost of expression in vertical cases 14% (9 of 65), P = 0.002; whereas p16(INK4a) (89% in vertical versus 71% in metastatic cases, P = 0.009) and p27(KIP1) (76% in radial versus 45% in vertical cases, P = 0.010) were diminished in advanced stages. The study also defines a combination of biological markers associated with shorter overall survival in patients with vertical growth phase melanoma, that provided a predictor model with four antibodies (Ki67, p16(INK4a), p21(CIP1), and Bcl-6). This predictor model was validated using an independent series of 72 vertical growth phase melanoma patients.