Melanoma is visible unlike other types of cancer, but it is still challenging to diagnose correctly because of the difficulty in distinguishing between benign nevus and melanoma. We conducted a robust investigation of melanoma, identifying considerable differences in local elastic properties between nevus and melanoma tissues by using atomic force microscopy (AFM) indentation of histological specimens. Specifically, the histograms of the elasticity of melanoma displayed multimodal Gaussian distributions, exhibiting the heterogeneous mechanical properties, in contrast with the unimodal distributions of elasticity in the benign nevus. We identified this notable signature was consistent regardless of blotch incidence by sex, age, anatomical site (e.g., thigh, calf, arm, eyelid, and cheek), or cancer stage (I, IV, and V). In addition, we found that the non-linearity of the force-distance curves for melanoma is increased compared to benign nevus. We believe that AFM indentation of histological specimens may technically complement conventional histopathological analysis for earlier and more precise melanoma detection.