Primary malignant melanoma of the anus and rectum is a rare and aggressive neoplasm that tends to invade locally and metastasize early in the course of the disease. It is often misdiagnosed as hemorrhoids or as one of the other benign anorectal conditions and is thus linked to an overall poor prognosis and a 5-year survival rate of less than 20%. Optimal treatment is still controversial, and current evidence does not show any preferential survival benefit from abdominoperineal resection over wide local excision. Chemotherapy or radiotherapy may be used for advanced disease. We report a 71-year-old female presenting with painful bowel movements and blood in stools. She was eventually found to have a mass arising from the anorectal junction with regional lymph node involvement. The patient underwent an abdominoperineal resection and is currently scheduled for chemotherapy.