Many women suffering from fibroids report fatigue. Chronic fatigue is one of the most common symptoms of iron deficiency (anemia), which is often a result of heavy fibroid bleeding.