Data on the relevance of anemia in heart failure (HF) patients with an ejection fraction (EF) > 40% by subgroup—preserved (HFpEF), mildly reduced (HFmrEF) and the newly defined recovered EF (HFrecEF)—are scarce. Patients with HF symptoms, elevated NT-proBNP, EF ≥ 40% and structural abnormalities were registered in the HFpEF-HFmrEF database. We described the outcome of our HFpEF-HFmrEF cohort by the presence of anemia. Additionally, HFrecEF patients were also selected from HFrEF patients who underwent resynchronization and, as responders, reached 40% EF. Using propensity score matching (PSM), 75 pairs from the HFpEF-HFmrEF and HFrecEF groups were matched by their clinical features. After PMS, we compared the survival of the HFpEF-HFmrEF and HFrecEF groups. Log-rank, uni-and multivariate regression analyses were performed. From 375 HFpEF-HFmrEF patients, 42 (11%) died during the median follow-up time of 1.4 years. Anemia (HR 2.77; 95%CI 1.47–5.23; p p = 0.01). Through PSM, the outcomes for HFpEF-HFmrEF and HFrecEF patients with anemia were poor, exhibiting no significant difference. In HFpEF-HFmrEF, anemia was an independent mortality predictor. Its presence multiplied the mortality risk in those with EF ≥ 40%, regardless of HF etiology.