Preclinical data showed anticancer effects of statins in melanoma, but meta-analyses could not demonstrate a reduced melanoma incidence in statin users. Rather than preventing occurrence, statins might reduce growth and metastatic spread of melanomas and ultimately improve survival. In this population-based study, we investigated the relationship between statin use and survival of melanoma patients. Patients ≥18 years who were diagnosed with cutaneous melanoma (Breslow thickness >1 mm) and registered in the Eindhoven Cancer Registry and in PHARMO Database Network between 1 January 1998 and 31 December 2010 were eligible. The hazard ratio (HR) of all-cause mortality was calculated by employing adjusted time-dependent and time-fixed Cox proportional hazard models. Disease-specific survival was estimated by means of 3-year relative survival rates (RSR). A control cohort of randomly selected patients using statins from PHARMO Database Network matched on age and gender was used to compare RSR of statin users to the general population. After melanoma diagnosis, 171 of 709 patients used statins. Use of statins showed a nonsignificantly decreased hazard of death (adjusted HR 0.76, 95% confidence interval [CI] 0.50–1.61). After stratification for gender, male but not female statin users showed a favorable outcome compared to nonusers (HR 0.57, 95% CI 0.32–0.99; HR 1.22, 95% CI 0.62–2.38, respectively). Three-year RSR for male statin users tended to be higher than for nonusers (91% vs. 80.5%, P = 0.06), no differences were observed in women (87.1% vs. 92.5%, P = 0.76). Statin use was not associated with an improved survival of melanoma patients. The trend for better survival of male in contrast to female statin users warrants further research.