The cancer stem cell hypothesis suggests that mutated melanocyte stem cells are present in skin as precursors of melanoma cells. Nestin and CD133 have been described as markers of melanocytic stem cells. The aim of this study was to establish if melanocytic stem cells could have a prognostic significance in melanoma progression. An immunohistochemical study for nestin and CD133 was performed in 130 primary tumors and 32 nodal metastasis biopsy specimens to evaluate possible differences, and to compare the results with survival data and clinicopathological variables. Nestin was expressed in cytoplasm of non-pigmented tumor cells and in endothelial cells, especially at the invading tumor front. Nestin staining in stage I and II (according to the American Joint Committee on Cancer Staging system) melanoma patients significantly predicted poor survival (log-rank test, P=0.037), with lower survival rates in cases with nestin positivity in both tumoral and endothelial cells. CD133 staining was not associated with survival. There were no significant differences in nestin or CD133 expression between primary tumors and metastases. These results suggest that nestin expression in both tumoral and endothelial cells may be considered an important early prognostic marker in melanoma.