Regression in melanoma is an immunological phenomenon that results in partial or complete replacement of the tumor with variably vascular fibrous tissue, often accompanied by pigment-laden macrophages and chronic inflammation. In some cases, tumor-infiltrating lymphocytes (TILs) may represent the earliest phase of this process. The prognostic significance of regression has long been a matter of debate, with inconsistent findings reported in the literature to date. This study sought to determine whether regression in primary cutaneous melanomas predicted sentinel lymph node (SLN) status and survival outcomes in a large cohort of patients managed at a single centre. Clinical and pathological parameters for 8,693 consecutive cases were retrieved. Associations between regression and SLN status, overall survival (OS), melanoma-specific survival (MSS) and recurrence-free survival (RFS) were investigated using logistic and Cox regression. Histological evidence of regression was present in 1958 cases (22.5%). Regression was significantly associated with lower Breslow thickness, lower mitotic rate, and absence of ulceration (p < 0.0001). Multivariable analysis showed that regression in combination with TILs independently predicted a negative SLN biopsy (OR 0.33; 95% C.I. 0.20-0.52; p < 0.0001). Patients whose tumors showed both regression and TILs had the highest 10-year OS (65%, 95% C.I. 59-71%), MSS (85%, 95% C.I. 81-89%), and RFS (60%, 95% C.I. 54-66%). On multivariable analyses, the concurrent presence of regression and TILs independently predicted the lowest risk of death from melanoma (HR 0.69; 95% C.I. 0.51-0.94; p = 0.0003) as well as the lowest rate of disease recurrence (HR 0.71; 95% C.I. 0.58-0.85; p < 0.0001). However, in contrast, in the subgroup analysis of Stage III patients, the presence of regression predicted the lowest OS and RFS, with MSS showing a similar trend. Overall, these findings indicate a prognostically favorable role of regression in primary cutaneous melanoma. However, in Stage III melanoma patients, regression may be a marker of more aggressive disease.