Proteus syndrome is a rare, sporadic disorder that causes postnatal overgrowth of multiple tissues in a mosaic pattern. Characteristic manifestations include: overgrowth and hypertrophy of limbs and digits, connective tissue nevus, epidermal nevus and hyperostoses. Various benign and malignant tumors and hamartomas may complicate the clinical course of patients with the syndrome. Commonly encountered tumors include hemangiomas, lymphangiomas and lipomas. Tumors of the genital tract occur less often. Bilateral ovarian cystadenomas are regarded as having diagnostic value in Proteus syndrome when occurring within the first two decades of life. We describe a 3-year-old girl with Proteus syndrome who developed bilateral paraovarian villoglandular endometrioid cystadenomatous tumors of borderline malignancy (low malignant potential) of the broad ligament. Desmoplastic tumor implants, presumably noninvasive, were present in biopsies from the pelvic floor, cul-de-sac and omentum. This is the first recognized example of a cystic borderline epithelial tumor of the female genital tract and the first paraovarian tumor reported in a patient with Proteus syndrome. Previously reported tumors and cystic lesions involving the female genital tract and the male genital tract in patients with Proteus syndrome are reviewed. We suspect that specific testicular and paratesticular tumors may prove to have the same diagnostic value in Proteus syndrome as do bilateral cystic ovarian and paraovarian tumors.