A substantial part of cutaneous malignant melanomas develops from benign nevi. However, the precise molecular events driving the transformation from benign to malignant melanoma are not well understood. We used laser microdissection and mass spectrometry to analyze the proteomes of melanoma subtypes, including superficial spreading melanomas (SSM, n=17), nodular melanomas (NM, n=17), and acral melanomas (AM, n=15). Furthermore, we compared the proteomes of nevi cells and melanoma cells within the same specimens (nevus-associated melanoma (NAM, n=14)). In total, we quantified 7,935 proteins. Despite the genomic and clinical differences of the melanoma subtypes, our analysis revealed relatively similar proteomes, except for the upregulation of proteins involved in immune activation in NM vs AM. Examining NAM versus nevi, we found 1,725 differentially expressed proteins (FDR < 0.05). Among these proteins were 140 that overlapped with cancer hallmarks, tumor suppressors, and regulators of metabolism and cell cycle. Pathway analysis indicated aberrant activation of the PI3K-AKT-mTOR pathways and the Hippo-YAP pathway. Using a classifier, we identified six proteins capable of distinguishing melanoma from nevi samples. Our study represents a comprehensive comparative analysis of the proteome in melanoma subtypes and associated nevi, offering, to our knowledge, previously unreported insights into the biological behavior of these distinct entities.