Uterine leiomyomas are highly prevalent and symptomatic tumors of women in their reproductive years. The morbidity caused by these tumors is directly related to increasing size. Leiomyoma cells do not rapidly proliferate; instead, the tumors grow primarily due to excessive production of disorganized extracellular matrix (ECM). The aberrant ECM results from excessive production of collagen subtypes and proteoglycans, increased profibrotic cytokines including transforming growth factors β1 and β3, and decreased or disrupted matrix metalloproteinases. These alterations result in the development of an ECM that is exceptionally stable. As a result, therapeutic interventions must redirect leiomyoma cells toward extracellular matrix dissolution, rather than solely inhibiting cell proliferation. Gonadotropin-releasing hormone analogues and selective progesterone receptor modulators with demonstrated clinical efficacy provide such a change in abnormal extracellular matrix formation by leiomyoma cells, inhibiting and reversing the fibrotic process. Novel therapies using pathways distinct from gonadal hormones, including antifibrotics, retinoic acid, peroxisome-proliferator-activated receptor γ ligands, and curcumin, provide promise for a future with improved therapeutic options for women suffering from uterine leiomyomas.