Primary melanoma of the vagina is a rare and very aggressive tumor with an incidence of only 0.46 per one million women per year and less than 250 cases reported in the literature. Here the authors present a case of a 60-year-old woman, gravida 5, para 5, postmenopausal by 28 years, admitted to the Clinic for Obstetrics and Gynecology, with recurrent vaginal bleeding for the last year and with the complaint of a palpable tumor near the vaginal introitus. The preoperative biopsy revealed melanoma. CT scan did not prove she had distant metastasis. The patient was treated surgically, with wide local excision of four x five cm measured lesion and safety margins of two cm. Bilateral inguinal lymphadenectomy was performed. Follow-up five months after initial diagnosis, revealed no evidence of local recurrency or distant metastasis.