We report the case of a 40-year-old woman who presented with a large perineal mass with no rectal or vaginal involvement. Imaging could not rule out malignancy. She underwent wide surgical excision. Histological analysis revealed a large atypical leiomyoma, measuring 24 × 12 × 8 cm. Followup after two years showed no recurrence and she has been asymptomatic since surgery. This is the largest perineal leiomyoma reported so far.