Loss-of-function germline mutations in the fumarase (FH) gene of the Krebs cycle characterize hereditary leiomyomatosis and renal cell cancer syndrome. Fumarase (FH) deficiency can be diagnosed by the loss of immunohistochemical expression. In this study, we investigated the occurrence and clinicopathologic features of FH-deficient uterine smooth muscle tumors (SMTs). A total of 1583 uterine and 157 nonuterine SMTs were examined using a polyclonal FH antibody and automated immunohistochemistry, and 86 uterine leiomyomas with an FH loss were identified. The frequencies of FH deficiency for subcohorts of uterine SMTs were 1.6% for unselected nonatypical leiomyomas, 1.8% for cellular leiomyomas, 37.3% for atypical leiomyomas, and 0% for leiomyosarcomas. One extrauterine, retroperitoneal estrogen receptor-positive leiomyoma was also FH deficient. The patient age of FH-deficient uterine leiomyomas was 20 to 52 years (median, 38 y). Grossly, these tumors were often soft and amorphous resembling a fibrothecoma. Histologically, the FH-deficient nonatypical leiomyomas lacked cellular packeting and distinct collagenous zones and showed chain-like or palisading nuclear arrangements, prominent staghorn-shaped blood vessels, oval nuclei with no or at most mild atypia, small eosinophilic nucleoli, and a low mitotic rate (0 to 1/10 HPF). The FH-deficient atypical leiomyomas had nuclear atypia often manifesting as multinucleation, prominent eosinophilic nucleoli, and mitotic activity up to 7/10 HPF, with atypical mitoses seen in 32% of cases. However, similar histologic changes were seen in some non-FH-deficient atypical leiomyomas. Loss-of-function FH-gene mutations including 5 whole-gene deletions and 3 frameshift mutations were identified in 8 of 16 FH-deficient nonatypical leiomyomas using multiplex ligation-dependent probe amplification and Sanger sequencing, respectively. Follow-up data on patients with FH-deficient atypical uterine leiomyomas revealed 19 patients alive (median follow-up 27 y) and 5 patients dead. Deaths occurred 9 to 30 years after surgery at a median age of 72 years; causes of death could not be determined. These results indicate that FH-deficient uterine leiomyomas occur with a high frequency among atypical leiomyomas and infrequently in nonatypical leiomyomas and are often histologically distinctive. They seem to have a low biological potential and lack any significant association with leiomyosarcoma.