Background: Currently, there remains an incomplete view of cancer stem cells (CSCs) in solid tumours. Methods: We studied a panel of putative CSC surface markers (ALDH1A1, ABCG2, CD44v7/8, CD44v10, CD133, CD271, and Nestin) in 40 established melanoma cell lines and four early-passage melanoma strains by flow cytometry. We additionally examined 40 formalin-fixed paraffin-embedded melanoma tissues using immunofluorescence microscopy. This was compared with their expression in healthy skin, normal differentiated melanocytes and fibroblasts. Results: Most of the putative CSC markers were expressed by both melanoma cell lines and tissues. When present, these proteins were expressed by the majority of cells in the population. However, the expression of these markers by cells in healthy skin sections, normal differentiated melanocytes, and fibroblasts revealed that differentiated non-malignant cells also expressed CSC markers indicating that they lack of specificity for CSCs. Culturing cell lines under conditions more characteristic of the tumour microenvironment upregulated CSC marker expressions in a proportion of cell lines, which correlated with improved cell growth and viability. Conclusions: The testing of melanoma cell lines (n = 40), early-passage cell strains (n = 4), and melanoma tissues (n = 40) showed that several putative CSC markers (ALDH1A1, ABCG2, CD44v7/8, CD44v10, CD133, CD271, and Nestin) are commonly present in a large proportion of melanoma cells in vitro and in situ. Further, we showed that these putative markers lack specificity for CSCs because they are also expressed in differentiated non-malignant cell types (melanocytes, fibroblasts, and skin), which could limit their use as therapeutic targets. These data are consistent with the emerging notion of CSC plasticity and phenotype switching within cancer cell populations.