(1) Background: Nevus-associated cutaneous melanoma (CM) is relatively common in the clinical practice of dermatopathologists. The correct diagnosis and staging of nevus-associated cutaneous melanoma (CM) mainly relies on the correct discrimination between benign and malignant cells. Recently, PRAME has emerged as a promising immunohistochemical marker of malignant melanocytes. (2) Methods: PRAME immunohistochemistry (IHC) was performed in 69 cases of nevus-associated CMs. Its expression was evaluated using a score ranging from 0 to 4+ based on the percentage of melanocytic cells with a nuclear expression. PRAME IHC sensitivity, specificity, positive predictive values, and negative predictive values were assessed. Furthermore, the agreement between morphological data and PRAME expression was evaluated for the diagnosis of melanoma components and nevus components. (3) Results: PRAME IHC showed a sensitivity of 59%, a specificity of 100%, a positive predictive value of 100%, and a negative predictive value of 71%. The diagnostic agreement between morphology and PRAME IHC was fair (Cohen’s Kappa: 0.3); the diagnostic agreement regarding the benign nevus components associated with CM was perfect (Cohen’s Kappa: 1.0). PRAME was significantly more expressed in thick invasive CMs than in thin cases (p = 0.02). (4) Conclusions: PRAME IHC should be considered for the diagnostic evaluation of nevus-associated CM and is most useful in cases of thick melanomas. Pathologists should carefully consider that a PRAME-positive cellular population within the context of a nevus could indicate a CM associated with the nevus. A negative result does not rule out this possibility.