To characterize the relationship between self-reported bleeding symptoms and uterine leiomyoma size and location. The leiomyoma status of a randomly selected sample of women aged 35–49 in the Washington, DC, area was determined using abdominal and transvaginal ultrasound to measure size and location of leiomyomata found at screening. Women were asked about symptoms of heavy bleeding (gushing-type bleeding, long menses, pad/tampon use) in a telephone interview. Using multivariable regression, we examined the relationships between leiomyoma characteristics and heavy bleeding symptoms among 910 premenopausal women. Women with leiomyomata (n = 596) were more likely to report gushing-type bleeding than women without leiomyomata; risk increased with leiomyoma size. Adjusted relative risks with 95% confidence intervals (CI) for women in each leiomyoma size category compared with the reference category (women without leiomyomata) were as follows: adjusted relative risk of 1.4 (95% CI 1.1, 1.9) for diffuse only, adjusted relative risk of 1.4 (95% CI 1.1, 1.8) for small leiomyomata (less than 2 cm), adjusted relative risk of 1.6 (95% CI 1.3, 2.0) for medium leiomyomata (2–5 cm), and adjusted relative risk of 1.9 (95% CI 1.5, 2.5) for large leiomyomata (greater than 5 cm). Reported use of eight or more pads/tampons on the heaviest days of menstrual bleeding increased with leiomyoma size, with a nearly 2.5-fold risk for women with large leiomyomata compared with women without leiomyomata (adjusted relative risk of 2.4; 95% CI 1.8, 3.1). Nonsubmucosal leiomyomata were associated with essentially the same increase in heavy bleeding as submuscosal leiomyomata of similar size. Small leiomyomata were associated with increased risk of heavy bleeding, and risk increased with size. Contrary to published articles, nonsubmucosal leiomyomata were associated with heavy bleeding to the same extent as submucosal leiomyomata.