Cutaneous deep penetrating melanocytic neoplasms frequently simulate melanoma and might occasionally progress to metastatic melanoma. Distinguishing deep penetrating nevi (DPN) and deep penetrating melanocytomas (DPM) from malignant deep penetrating tumors (MDPT) is difficult based on histopathology alone, and diagnostic criteria for MDPT are currently lacking. Using a molecular workup, we aimed to provide readily available diagnostic tools for classification of deep penetrating tumors. We used clinical follow-up and Single Nucleotide Polymorphism (SNP) array for tumor classification of 20 deep penetrating neoplasms to identify associations with histopathological, immunohistochemistry, and NGS findings. Ten neoplasms were classified as MDPT, four as DPM, and six as DPN. Two MDPT showed metastases. The following parameters were statistically significantly associated with MDPT: severe nuclear atypia (risk ratio [RR] 2.9, p < 0.05), absence of a nevus component (RR 10.0, p = 0.04), positive PRAME expression (RR 9.0, p = 0.02), complete loss of p16 expression (RR 3.5, p = 0.003), TERT-p and APC mutations (RR 11.0, p = 0.01 and RR 2.7, p = 0.002, respectively), and ≥1 additional pathogenic mutation (RR 9.0, p = 0.02). Ki-67 expression ≥ 5% was not significantly associated with MDPTs, although it was <5% in all DPNs. Three MDPT did not show nuclear β-catenin expression despite having a CTNNB1 (n = 2) or an APC mutation (n = 1). Our findings suggest that complete loss of p16 and positive PRAME expression, a driver mutation in APC, ≥ 1 additional pathogenic mutation, especially in TERT-p, support an MDPT diagnosis in deep penetrating neoplasms. Besides severe nuclear atypia and possibly severe inflammation, we did not identify specific histopathological criteria for malignancy. Non-aberrant nuclear β-catenin expression might not exclude a deep penetrating signature in MDPT.