Objective: To investigate the clinical, pathological, and genetic characteristics of patients with vaginal melanoma in a nationwide setting. Materials/methods: All patients diagnosed with vaginal melanoma from 1980 to 2018 were collected by searching the digital archives of the Danish Registry of Pathology (Patobank). Patient specimens were examined, the histological diagnoses were validated, and targeted next-generation sequencing (NGS) of known frequent hot spots in 163 genes was performed. Results: Fifty-two patients were included. The incidence for primary melanoma of the vagina in the Danish population (5.5 million people) was calculated to be 0.24 cases/million/year from 1980 to 2018. For all patients, the median OS was 17.5 months (95% CI: 13.0–24.0), and the 5-year OS was 19.4% (95% CI: 10.9–34.3). We identified frequent mutations in ATRX (7/25 cases) and TP53 (7/25 cases). Mutations found in TP53 were associated with a significant decrease in OS (p = 0.043), whereas mutations in the ATRX gene alone did not show a significant impact on OS (p = 0.3649). Patients who harbored co-mutations in both ATRX and TP53 showed a significant reduction in OS (p = 0.0081), with a median OS of 9.5 months compared to 20 months in those without the co-mutation. Conclusions: Vaginal melanoma is a rare disease with a poor prognosis presumably due to vague symptoms and the anatomical location of the disease. Co-mutations in ATRX and TP53 and mutations in TP53 alone were associated with a poor prognosis, and these genes are potentially interesting targets for future therapy.