About half of the melanomas are detected by patients but the mean thickness of such melanomas is higher than when diagnosed by physicians. Symptoms and signs described by patients are dynamic changes and pruritus, the appearance of a new lesion having been rarely investigated. These observations are documented for melanomas but not for benign naevi. To the best of our knowledge, this is the first study in which both melanomas and suspected excised naevi were included. The main objectives were to (a) analyse the value of the anamnestic predictors for melanoma versus non-melanoma and (b) calculate the influence of age on the most significant anamnestic predictors. In order to reach these objectives, we prospectively collected data on symptoms (pruritus, anxiety) and signs (de novo appearance, dynamic changes and bleeding) described by patients undergoing the excision of lesions clinically diagnosed as melanocytic and considered as suspicious by 46 Belgian dermatologists. Among 1865 lesions, dynamic changes and de novo appearance were significant predictors for melanoma versus non-melanoma diagnosis in all patients and patients older than 50, respectively. More precisely, dynamic changes and de novo appearance occurred to be strong predictors for melanoma diagnosis in patients greater than 41.5 and greater than 44.5 years, respectively. Pruritus was not significant for melanoma diagnosis. As a conclusion, when mid-age or older patients observe melanocytic lesions as recently changed or newly appeared, such lesions should be considered more carefully than when observed by young patients.