The intrinsic biomechanical properties of cancer cells remain poorly understood. To decipher whether cell stiffness modulation could increase melanoma cells’ invasive capacity, we performed both in vitro and in vivo experiments exploring cell stiffness by atomic force microscopy (AFM). We correlated stiffness properties with cell morphology adaptation and the molecular mechanisms underlying epithelial-to-mesenchymal (EMT)-like phenotype switching. We found that melanoma cell stiffness reduction was systematically associated with the acquisition of invasive properties in cutaneous melanoma cell lines, human skin reconstructs, and Medaka fish developing spontaneous MAP-kinase-induced melanomas. We observed a systematic correlation of stiffness modulation with cell morphological changes towards mesenchymal characteristic gains. We accordingly found that inducing melanoma EMT switching by overexpressing the ZEB1 transcription factor, a major regulator of melanoma cell plasticity, was sufficient to decrease cell stiffness and transcriptionally induce tetraspanin-8-mediated dermal invasion. Moreover, ZEB1 expression correlated with Tspan8 expression in patient melanoma lesions. Our data suggest that intrinsic cell stiffness could be a highly relevant marker for human cutaneous melanoma development.