Primary anorectal melanoma is a rare, but aggressively malignant tumor. The most common manifestation is lower gastrointestinal bleeding. We report a case of a 70-year-old female with cirrhosis of liver who presented with hematochezia, and on Colonoscopy was found to have a brown-grayish protruding anorectal mass that proven to be a melanoma. A series of imaging studies revealed no evidence of extra-luminal invasion, lymph node metastasis, and distant dissemination of tumor. Thereafter, the tumor was removed by trans-anal excision. The patient remained well without any evidence of tumor recurrence during a 30-month follow-up. We suggest that primary anorectal melanoma should be suspected in patients with concomitant presence of lower gastrointestinal bleeding and pigmented anorectal tumor. In order to preserve quality of life, and lessen operative morbidity, a conservative local excision might be a treatment option for primary anorectal melanoma, particularly in debilitated patients.