Melanoma in advanced stages is one of the most aggressive tumors and the deadliest of skin cancers. To date, the histopathological staging focuses on tumor thickness, and clinical staging is a major estimate of the clinical behavior of primary melanoma. Here we report on an observational study with in-depth molecular profiling at the protein level including post-translational modifications (PTMs) on eleven primary tumors from melanoma patients. Global proteomics, phosphoproteomics, and acetylomics were performed on each sample. We observed an up-regulation of key mitochondrial functions, including the mitochondrial translation machinery and the down-regulation of structural proteins involved in cell adhesion, the cytoskeleton organization, and epidermis development, which dictates the progression of the disease. Additionally, the PTM level pathways related to RNA processing and transport, as well as chromatin organization, were dysregulated in relation to the progression of melanoma. Most of the pathways dysregulated in this cohort were enriched in genes differentially expressed at the transcript level when similar groups are compared or metastasis to primary melanomas. At the genome level, we found significant differences in the mutation profiles between metastatic and primary melanomas. Our findings also highlighted sex-related differences in the molecular profiles. Remarkably, primary melanomas in women showed higher levels of antigen processing and presentation, and activation of the immune system response. Our results provide novel insights, relevant for developing personalized precision treatments for melanoma patients.