During the process of metastasis, cancer cells dissociate from primary tumors, migrate to distal sites, and finally colonize, eventually leading to the formation of metastatic tumors. These cancer cells, defined circulating tumor cells (CTCs) spreading through the blood stream, may develop metastatic lesions or remain dormant. Some emerging clinical evidence supports that some tumor cells may possess metastatic properties already in the earlier stages of tumorigenesis. Because the initiation and progression of vertical growth in human melanoma is fundamental to the notion of tumor virulence and progression, we decided to immune-magnetic collect and molecularly characterize circulating melanoma cells (CMCs) from melanoma patients AJCC staged = pT1b (i.e., transition from radial to vertical phase). CMCs are phenotypically and molecularly heterogeneous, thus we performed a "home-made Liquid-Biopsy," by targeting the melanoma-associated-antigen, MCAM/MUC18/CD146, and/or the melanoma-initiating marker, ABCB5. We assessed a biomarker qualitative expression panel, contemplating the angiogenic-potential, melanoma-initiating and melanoma-differentiation drivers, cell-cell adhesion molecules, matrix-metallo-proteinases, which was performed on three enriched subpopulations from a total of 61 blood-samples from 21 melanoma patients. At first, a significant differential expression of the specific transcripts was documented between and within the CMC fractions enriched with MCAM-, ABCB5-, and both MCAM/ABCB5-coated beads, when analyzing two distinct groups: early AJCC- (stage I-II) and advanced- staged patients (stage II-IV). Moreover, in the early-AJCC staged-group, we could distinguish "endothelial," CD45MCAM enriched-, "stem" S-CMCs, CD45ABCB5 enriched- and a third hybrid bi-phenotypic CD45MCAM/ABCB5 enriched-fractions, due to three distinct gene-expression profiles. In particular, the endothelial-CMCs were characterized by positive expression of genes involved in migration and invasion, whilst the stem CMC-fraction only expressed stem and differentiation markers. The third subpopulation isolated based on concurrent MCAM and ABCB5 protein expression showed an invasive phenotype. All three distinct CMCs sub-populations, exhibited a primitive, "stem-mesenchymal" profile suggesting a highly aggressive and metastasizing phenotype. This study confirms the phenotypic and molecular heterogeneity observed in melanoma and highlights those putative genes involved in early melanoma spreading and disease progression.