Vesico-rectal fistulas are rare conditions, but they significantly affect patients’ quality of life and are frequently secondary to the complex cancer treatment in the organs of the pelvis minor or a local progression of the malignant process. They are among the most disabling complications requiring individualized treatment by a highly experienced multidisciplinary team. However, the treatment is frequently applied too late, and the disease frequently recurs. Complex surgical interventions are often contraindicated because of the progressing malignancy or the previously applied therapy (radiological or surgical). In such cases, the success of the treatment frequently depends on the selection of a novel less invasive technique. This clinical case illustrates successful treatment of the vesico-rectal fistula with favorable outcomes of the first-time application of bilateral retroperitoneoscopic ureterocutaneostomy.