Background: Cognitive impairment (CI) is estimated to be present in 25%–80% of heart failure (HF) patients, but its prevalence at diagnosis is unclear. To improve our understanding of cognition in HF, we determined the prevalence of CI among adults with incident HF in the REGARDS study. Methods and Results: REGARDS is a longitudinal cohort study of adults ≥45 years of age recruited in the years 2003–2007. Incident HF was expert adjudicated. Cognitive function was assessed with the Six-Item Screener. The prevalence of CI among those with incident HF was compared with the prevalence of CI among an age-, sex-, and race-matched cohort without HF. The 436 participants with incident HF had a mean age of 70.3 years (SD 8.9), 47% were female, and 39% were black. Old age, black race, female sex, less education, and anticoagulation use were associated with CI. The prevalence of CI among participants with incident HF (14.9% [95% CI 11.7%–18.6%]) was similar to the non-HF matched cohort (13.4% [11.6%–15.4%]; P <.43). Conclusions: A total of 14.9% of the adults with incident HF had CI, suggesting that the majority of cognitive decline occurs after HF diagnosis. Increased awareness of CI among newly diagnosed patients and ways to mitigate it in the context of HF management are warranted.