Background: Over the past two decades, there has been a rising trend in malignant melanoma incidence worldwide. In 2008, Germany introduced a nationwide skin cancer screening program starting at age 35. The aims of this study were to analyse the distribution of malignant melanoma tumour stages over time, as well as demographic and regional differences in stage distribution and survival of melanoma patients. Methods: Pooled data from 61 895 malignant melanoma patients diagnosed between 2002 and 2011 and documented in 28 German population-based and hospital-based clinical cancer registries were analysed using descriptive methods, joinpoint regression, logistic regression and relative survival. Results: The number of annually documented cases increased by 53.2% between 2002 (N = 4 779) and 2011 (N = 7 320). There was a statistically significant continuous positive trend in the proportion of stage UICC I cases diagnosed between 2002 and 2011, compared to a negative trend for stage UICC II. No trends were found for stages UICC III and IV respectively. Age (OR 0.97, 95% CI 0.97-0.97), sex (OR 1.18, 95% CI 1.11-1.25), date of diagnosis (OR 1.05, 95% CI 1.04-1.06), 'diagnosis during screening' (OR 3.24, 95% CI 2.50-4.19) and place of residence (OR 1.23, 95% CI 1.16-1.30) had a statistically significant influence on the tumour stage at diagnosis. The overall 5-year relative survival for invasive cases was 83.4% (95% CI 82.8-83.9%). Conclusions: No distinct changes in the distribution of malignant melanoma tumour stages among those aged 35 and older were seen that could be directly attributed to the introduction of skin cancer screening in 2008.