Stem cell-like cells have recently been identified in melanoma cell lines, but their relevance for melanoma pathogenesis is controversial. To characterize the stem cell signature of melanoma, expression of stem cell markers BMI-1 and nestin was studied in 64 cutaneous melanomas, 165 melanoma metastases as well as 53 melanoma cell lines. Stem cell renewal factor BMI-1 is a transcriptional repressor of the Ink4a/Arf locus encoding p16(ink4a) and p14(Arf). Increased nuclear BMI-1 expression was detectable in 41 of 64 (64%) primary melanomas, 117 of 165 melanoma metastases (71%) and 15 of 53 (28%) melanoma cell lines. High nestin expression was observed in 14 of 56 primary melanomas (25%), 84 of 165 melanoma metastases (50%) and 21 of 53 melanoma cell lines (40%). There was a significant correlation between BMI-1 and nestin expression in cell lines (p = 0.001) and metastases (p = 0.02). These data indicate that cells in primary melanomas and their metastases may have stem cell properties. Cell lines obtained from melanoma metastases showed a significant higher BMI-1 expression compared to cell lines from primary melanoma (p = 0.001). Further, primary melanoma lacking lymphatic metastases at presentation (pN0, n = 40) was less frequently BMI-1 positive than melanomas presenting with lymphatic metastases (pN1; n = 24; 52% versus 83%; p = 0.01). Therefore, BMI-1 expression appears to induce a metastatic tendency. Because BMI-1 functions as a transcriptional repressor of the Ink4a/Arf locus, p16(ink4a) and p14(Arf) expression was also analyzed. A high BMI-1/low p16(ink4a) expression pattern was a significant predictor of metastasis by means of logistic regression analysis (p = 0.005). This suggests that BMI-1 mediated repression of p16(ink4a) may contribute to an increased aggressive behavior of stem cell-like melanoma cells.