To investigate the early, poorly understood events driving metastatic progression, we searched for the earliest detectable disseminated cancer cells (DCCs), also often referred to as disseminated tumor cells (DTCs), in sentinel lymph node (SLN) biopsies of 492 patients with stage I–III melanoma. Using micromanipulator-assisted isolation of rare DCCs, single-cell mRNA and DNA sequencing, codetection by indexing immunofluorescence imaging and survival analysis, we identified melanoma-associated chondroitin sulfate proteoglycan (MCSP)+ melanoma cells as metastasis founder cells (MFCs). We found that DCCs entering SLNs predominantly exhibited a transitory phenotype that, upon interferon-γ exposure triggered by CD8 T cells, dedifferentiated into a neural-crest-like phenotype. This was accompanied by increased production of small extracellular vesicles (sEVs) carrying the immunomodulatory proteins CD155 and CD276 but rarely programmed cell death protein 1 ligand 1. The sEVs suppressed CD8 T cell proliferation and function, facilitating colony formation. Targeting MCSP+ MFCs or their immune escape mechanisms could be key to curing melanoma early by preventing manifestation of metastasis.