The CDKN2A (p16^INK4a) cell cycle-inhibitory gene has been associated with development of familial melanoma. Additionally, recent studies indicate that p16 alterations occur frequently in sporadic melanomas. To investigate whether differences in p16 expression are associated with tumor cell proliferation, tumor progression, and patient survival, we examined the immunohistochemical staining of p16 protein in a consecutive series of 202 vertical growth phase melanomas and 68 corresponding metastases and compared the results with Ki-67 expression, p53 expression,clinicopathological variables, and survival data. Forty-five percent of the primary tumors showed absent or minimal nuclear staining for p16 protein. These cases were significantly associated with high Ki-67 expression (P < 0.0001), ulceration(P = 0.001), and vascular invasion(P = 0.03). Further loss of p16 expression was observed in metastatic lesions (77% were negative; P < 0.0001). Absent/minimal nuclear p16 staining significantly predicted poor patient survival (log-rank test, P = 0.0003), with 37% and 67% estimated 10-year survival rates for cases with absent or present p16 expression,respectively. In multivariate analysis, p16 staining was an independent prognostic factor (hazard ratio, 2.5; 95% confidence interval,1.5–4.2; P = 0.0008), along with p53 expression,Ki-67 expression, anatomical site, Clark’s level of invasion, and vascular invasion. Our findings indicate that loss of nuclear p16 protein expression in vertical growth phase melanomas is associated with increased tumor cell proliferation (Ki-67) and independently predicts decreased patient survival. Cases without p53 expression had improved survival.