Background: Pelvic exenteration is an ultra-radical surgical procedure described by Brunschwig in 1948, which attempts to surgically cure patients with recurrent pelvic cancer after radiotherapy. Several variants of pelvic exenteration are described that allow a more limited or extensive resection, depending on the stage of the disease. Case report: We report the case of a 54-year-old woman, who was diagnosed with a tumoral rectovaginal fistula after a recurrent cervical cancer that had been treated with a total hysterectomy with bilateral adnexectomy and a left percutaneous nephrostomy, as well as interaortocaval lymph node resection. The patient had undergone a supralevator total pelvic exenteration with pelvic and interaortocaval lymphadenectomy. The reconstruction process included right ureterostomy, left nephrostomy, and colocutaneous anal anastomosis (Parks procedure). Conclusions: Supralevator total pelvic exenteration provides hope for cure in patients with pelvic malignancies that reappear after radiotherapy. The restoration of the digestive tract and avoiding colostomy with a colocutaneous anastomosis increases the quality of life in these cases.