Most cancers contain morphologically heterogeneous populations of cells. While this observation may partly be explained by the coexistence of multiple genetic sub-clones arising through independent somatic mutations and/or as a result of differentiation processes in the tumor microenvironment, it also implies that the tumor may be formed from undifferentiated ''stem cell-like'' cells called ''cancer stem cells'' or ''cancer-initiating cells''. These cells are thought to constitute one or several rare subpopulations in a given tumor and would be strongly responsible for initiation of tumor development and growth as well as for metastasis and recurrence after cytoreductive therapy. However, while the concept of cancer stem cells has been first established for human myeloid leukemia in the 1960s, it has only much later been extended to other solid tumors such as breast or brain cancers and most recently to melanoma. Thus, it is presently unclear which role a sufficiently characterized population of melanoma stem cells plays in cancer promotion and progression. Here, we review the emerging melanoma stem cell model and discuss the biological and therapeutic implications of the model.