Background: Influenza infection is a serious event for patients with heart failure (HF). Little knowledge exists about the association between influenza vaccination and outcome in patients with HF. This study sought to determine whether influenza vaccination is associated with improved long-term survival in patients with newly diagnosed HF. Methods: We performed a nationwide cohort study including all patients who were >18 years of age and diagnosed with HF in Denmark in the period of January 1, 2003, to June 1, 2015 (n=134 048). We collected linked data using nationwide registries. Vaccination status, number, and frequency during follow-up were treated as time-varying covariates in time-dependent Cox regression. Results: Follow-up was 99.8% with a median follow-up time of 3.7 years (interquartile range, 1.7-6.8 years). The vaccination coverage of the study cohort ranged from 16% to 54% during the study period. In unadjusted analysis, receiving ≥1 vaccinations during follow-up was associated with a higher risk of death. After adjustment for inclusion date, comorbidities, medications, household income, and education level, receiving ≥1 vaccinations was associated with an 18% reduced risk of death (all-cause: hazard ratio, 0.82; 95% CI, 0.81-0.84; P<0.001; cardiovascular causes: hazard ratio, 0.82; 95% CI, 0.81-0.84; P<0.001). Annual vaccination, vaccination early in the year (September to October), and greater cumulative number of vaccinations were associated with larger reductions in the risk of death compared with intermittent vaccination. Conclusions: In patients with HF, influenza vaccination was associated with a reduced risk of both all-cause and cardiovascular death after extensive adjustment for confounders. Frequent vaccination and vaccination earlier in the year were associated with larger reductions in the risk of death compared with intermittent and late vaccination.