A 57-year-old woman was admitted with lower abdominal pain and bloody bowel discharge. She was diagnosed with rectal tumor by colonoscopy, and a biopsy was performed. Surgery was performed, resulting in a diagnosis of rectal paraganglioma. Since recurrence was confirmed three years later, reoperation was done, and chemotherapy with cyclophosphamide, vincristine and dacarbazine (CVD) was subsequently carried out for further recurrence. After the administration of up to 15 courses of CVD, we delivered best supportive care due to disease progression. She died a year and a half after starting chemotherapy. We herein report this rare disease with a review of the relevant literature.