A large body of evidence in the scientific literature suggests that the numbers of common and atypical nevi are strong, independent risk factors for the occurrence of cutaneous malignant melanoma. Furthermore, some studies recently found an association between high nevus counts and an improved melanoma prognosis. The aim of this study was to investigate a possible relationship between the number of common and atypical nevi and melanoma prognostic factors. We carried out a retrospective analysis of patients with a histopathologically confirmed diagnosis of melanoma. These patients were treated at the Dermatology Clinic of the University of Florence from January 2000 to December 2013. The main analysis investigated the association of common and atypical nevi with Breslow thickness and ulceration. The number of nevi was investigated as a continuous variable and a categorical variable considering the median number of common nevi, given the skewness of the distribution of common nevi. We analyzed 818 melanoma patients treated from January 2000 to December 2013. We found a sex and nevi interaction: among women, thick melanomas occur more frequently in patients with a low common nevi count (<10); no association was found in men. This sex and nevi interaction was also found considering the association with very thick melanomas (Breslow > 4 mm). Moreover, the presence of an increasing number of atypical nevi was associated with increased risk of ulceration in both sexes. These data provide new perspectives in the differential sex-related biological behavior of melanoma among females and males.