The aim of this case-case study was to determine the differences between dysplastic and common naevus-associated melanomas (NAM) and de novo melanomas. A total of 1,021 prospectively collected patients with invasive cutaneous melanoma from an oncology referral centre were included in the study. Of these, 75.51% had de novo melanomas, 12.93% dysplastic NAM, and 11.56% common NAM. Dysplastic NAM, compared with de novo melanomas, were associated with intermittently photo-exposed sites, atypical melanocytic naevi, decreased tumour thickness, and presence of MC1R non-synonymous variants. Common NAM were more frequent on the trunk and of superficial spreading type. Comparison of dysplastic with common NAM showed significant difference only with regard to mitoses. Both subtypes of NAM shared less aggressive traits than de novo melanomas, albeit with no significant differences in survival after multivariate adjustment. In conclusion, NAM present with less aggressive traits, mostly due to a greater awareness among patients of changing moles than due to their intrinsic biological characteristics.