Most common reason for the vesicouterine fistula is a cesarean section; no cases were reported of degenerated uterine leiomyoma communicating with the urinary bladder. We report a case of fistulous communication between the degenerated leiomyoma and the bladder. The patient's initial clinical presentation was consistent with recurrent UTI. She underwent multiple examinations including cystoscopy, cystouretrography, retrograde pyeolography, and MRI. The ultimate treatment was an exploratory laparotomy and en-block resection of the bladder wall, fistula tract, and degenerated leiomyoma. Fistula can develop between the bladder and degenerated leiomyoma and could be one of the reasons for the chronic pelvic pain and dysuria.