Prognosis and survival for malignant melanoma is highly dependent on early diagnosis and treatment. While the American Joint Committee on Cancer (AJCC) criterion provides a means of staging melanomas and guiding treatment approaches, it is unable to identify the risk of disease progression of early stage tumors or provide reliable stratification for novel adjuvant therapies. The demand for credible prognostic/companion biomarkers able to identify high-risk melanoma subgroups as well as guide more effective personalized/precision-based therapy is therefore of paramount importance. Autophagy, the principle lysosomal-mediated process for the degradation/recycling of cellular debris, is a hot topic in cancer medicine, and observations of its deregulation in melanoma have brought its potential as a prognostic biomarker to the forefront of current research. Key regulatory proteins, including Atg8/microtubule-associated light chain 3 (LC3) and BECN1 (Beclin 1), have been proposed as potential prognostic biomarkers. However, given the dynamic nature of autophagy, their expression in vitro does not translate to their use as a prognostic biomarker for melanoma in vivo. We have recently identified the expression levels of Sequestosome1/SQSTM1 (p62) and activating molecule in Beclin 1-regulated autophagy protein 1 (AMBRA1) as novel independent prognostic biomarkers for early stage melanomas. While increasing followed by subsequent decreasing levels of p62 expression reflects the paradoxical role of autophagy in melanoma, expression levels additionally define a novel prognostic biomarker for AJCC stage II tumors. Conversely, loss of AMBRA1 in the epidermis overlying primary melanomas defines a novel prognostic biomarker for AJCC stage I tumors. Collectively, the definition of AMBRA1 and p62 as prognostic biomarkers for early stage melanomas provides novel and accurate means through which to identify tumors at risk of disease progression, facilitating earlier patient therapeutic intervention and stratification tools for novel personalized therapeutic approaches to improve clinical outcome.