Objectives: To determine the frequency of naevus-associated melanoma among superficial spreading and nodular subtypes; and to investigate associations between naevus-associated melanoma and other clinico-pathological characteristics. Design, setting and participants: Cross-sectional study of all patients with nodular and superficial spreading melanomas diagnosed between 1994 and 2015 at the Victorian Melanoma Service, Melbourne. Methods and main outcome measures: Clinical and pathological characteristics of naevus-associated and de novo melanomas were assessed in univariable and multivariable logistic regression analyses. Results: Of 3678 primary melanomas, 1360 (37.0%) were histologically associated with a naevus and 2318 (63.0%) were de novo melanomas; 71 of 621 nodular (11.4%) and 1289 of 3057 superficial spreading melanomas (42.2%) were histologically associated with a naevus. In multivariable analyses, the odds of being associated with a naevus were higher for melanomas located on the trunk (v head and neck: adjusted odds ratio [OR], 2.27; 95% CI, 1.73e2.96; P < 0.001), while the odds were lower for thicker tumours (adjusted OR, 0.75 per millimetre increase in Breslow thickness; 95% CI, 0.69e0.81; P < 0.001), amelanotic/hypomelanotic melanomas (adjusted OR, 0.68; 95% CI, 0.48e0.97; P = 0.035), and older age (patients 70 years or older v patients under 30 at diagnosis: adjusted OR, 0.28; 95% CI, 0.20e0.40; P < 0.001). After adjusting for confounders, the odds of an associated naevus was three times as high for superficial spreading melanomas as for nodular melanomas (adjusted OR, 3.05; 95% CI, 2.24e4.17; P < 0.001). Conclusion: Melanomas are most likely to arise in the absence of a pre-existing naevus, particularly nodular melanomas. Public health campaigns should therefore emphasise the detection of suspicious de novo lesions, as well as of changing lesions.