Rectovaginal fistula is usually a challenging condition for surgeons, but a fistula between the rectum and the neovagina in male-to-female transsexual is even more difficult to treat as it is a rare complication occurring in a patient with modified anatomy of the perineum, with heavy psychological implications for the patient. Here, we report a case of recurrent recto-neovaginal fistula in a male-to-female transsexual successfully treated by perineal graciloplasty.