Whether tumorigenic cancer stem cells (CSCs) exist in melanoma has been the focus of much controversy in recent years. A number of studies have pointed to the existence of melanoma cell sub-populations that act as CSCs and can be distinguished from other tumor cells based on specific surface marker expression or specific properties such as the capacity for extensive self-renewal. Other studies failed to identify melanoma stem cells and proposed that the potential to initiate tumors is a wide spread feature in melanoma inherent to most if not all cells of the tumor mass. As with normal stem cells, the term CSC is based on an operational definition, indicating not just a tumor-initiating cell, but also a cell with the capacity to sustain long-term tumor propagation. Therefore, the experimental set-up chosen to identify putative CSCs in melanoma is crucial: Both the method of tumor cell preparation and the procedure used to assess CSC properties in vivo influence the experimental outcome and hence its interpretation. In this review, we summarize our current knowledge on CSCs and the role of stem cell properties in melanoma and discuss recent findings with respect to their clinical relevance.