Background: Venous thromboembolism (VTE) is a sex-specific disease that has different presentations between men and women. Women with uterine leiomyoma can present with VTE without exhibiting the traditional risk factors. We investigated the relationship between a history of uterine leiomyoma and the risk of VTE using the National Health Insurance Research Database (NHIRD). Methods: We conducted a retrospective, nationwide, population-based case-control study using the NHIRD. We identified 2,282 patients with diagnosed VTE and 392,635 subjects without VTE from 2000 to 2013. After development of an age and index diagnosis year frequency-matchedmodel and propensity score-matched model, 2models with a case-to-control ratio of 1 to 4 were established. Using the diagnosis of uterine leiomyoma as the exposure factor, conditional logistic regression was performed to examine the association between uterine leiomyoma and VTE. Multiple logistic regression analysis was used to investigate the joint effect of uterine leiomyoma and comorbid diseases on the risk of VTE. Results: A strong association was observed between uterine leiomyoma and VTE in the overall patient model, frequency-matched model and propensity score-matched model [p < 0.0001, odds ratio (OR): 1.547; p = 0.0005, OR: 1.486; p = 0.0405, OR: 1.26, respectively]. In the subgroup analyses,women with uterine leiomyoma whowere  45 years old were less likely to experience VTE, but women with uterine leiomyoma and anemia, cancer, coronary artery disease or heart failure were more likely to experience VTE. Conclusions:Womenwith uterine leiomyomas have an increased risk of developing VTE, especially during reproductive periods or in the presence of specific diseases.