Lymph node (LN) status is an important prognostic factor in melanoma patients. p16 expression and proliferation rate (MIB-1) of primary melanomas have been suggested as a marker of metastatic potential. In this study, the correlation of p16 expression and the proliferation rate (MIB-1) with LN status and tumor-specific survival was investigated in primary melanomas. MIB-1 and p16 expression were analyzed by immunohistochemistry in 64 patients with primary cutaneous melanoma. Thirty four nevi were used as control. All patients underwent sentinel lymph node staging. Three different p16 staining patterns were observed: a combination of nuclear and cytoplasmic staining, only cytoplasmic staining and absence of p16 expression. All 34 nevi displayed a nuclear and cytoplasmic p16 staining, whereas p16 was negative in 14 of 64 (22%) melanomas. The level of p16 expression gradually decreased from benign nevi to melanoma without metastasis to melanoma with metastasis. There was a significant correlation between cytoplasmic p16 expression and absence of metastasis (p < 0.05). Death of disease correlated with absence of p16 immunostaining (p = 0.01). MIB-1 expression was not associated with survival. These results confirm the relevance of p16 expression as a prognostic marker in melanoma patients. In addition, it was shown that cytoplasmic immunostaining for p16 in primary melanoma might serve as a predictor of the LN status. Therefore, immunohistochemical evaluation for p16 expression is of potential value for treatment planning in melanoma surgery.