The role of p16 and p53 alterations in cutaneous melanoma has been recently discussed, but it remains to be clarified. In the present immunohistochemical study, the expression of p16 and p53 proteins and their possible prognostic relevance have been examined in 102 melanomas of the aggressive nodular type. Twelve percent showed a strong expression of p53 protein, and these cases were significantly more frequent in the head/neck area compared with other sites (32% vs. 6%). Expression of p16 protein was negative or weak in 9% of the cases, and this tended to be less frequent in head/neck tumors compared with the others (0% vs. 12%). Whereas p53 staining was not prognostically important, loss of p16 staining was significantly associated with markedly reduced recurrence free and patient survival in univariate analysis (product-limit method). In multivariate analysis, lack of p16 staining was significantly associated with recurrent disease (p = 0.013). Our findings indicate an important role of altered p16 protein expression in a subgroup of melanoma patients.