Ultraviolet radiation (UVR) damages the dermis and fibroblasts; and increases melanoma incidence. Fibroblasts and their matrix contribute to cancer, so we studied how UVR modifies dermal fibroblast function, the extracellular matrix (ECM) and melanoma invasion. We confirmed UVR-damaged fibroblasts persistently upregulate collagen-cleaving matrix metalloprotein-1 (MMP1) expression, reducing local collagen (COL1A1), and COL1A1 degradation by MMP1 decreased melanoma invasion. Conversely, inhibiting ECM degradation and MMP1 expression restored melanoma invasion. Primary cutaneous melanomas of aged humans show more cancer cells invade as single cells at the invasive front of melanomas expressing and depositing more collagen, and collagen and single melanoma cell invasion are robust predictors of poor melanoma-specific survival. Thus, primary melanomas arising over collagen-degraded skin are less invasive, and reduced invasion improves survival. However, melanoma-associated fibroblasts can restore invasion by increasing collagen synthesis. Finally, high COL1A1 gene expression is a biomarker of poor outcome across a range of primary cancers.