Patients with heart failure used to have an increased risk of stroke, but this may have changed with current treatment regimens. We assessed the association between heart failure and the risk of stroke in a population-based cohort that was followed since 1990. The study uses the cohort of the Rotterdam Study and is based on 7,546 participants who at baseline (1990–1993) were aged 55 years or over and free from stroke. The associations between heart failure and risk of stroke were assessed using time-dependent Cox proportional hazards models, adjusted for cardiovascular risk factors (smoking, diabetes mellitus, BMI, ankle brachial index, blood pressure, atrial fibrillation, myocardial infarction and relevant medication). At baseline, 233 participants had heart failure. During an average follow-up time of 9.7 years, 1,014 persons developed heart failure, and 827 strokes (470 ischemic, 75 hemorrhagic, 282 unclassified) occurred. The risk of ischemic stroke was more than five-fold increased in the first month after diagnosis of heart failure (age and sex adjusted HR 5.79, 95% CI 2.15–15.62), but attenuated over time (age and sex adjusted HR 3.50 [95% CI 1.96–6.25] after 1–6 months and 0.83 [95% CI 0.53–1.29] after 0.5–6 years). Additional adjustment for cardiovascular risk factors only marginally attenuated these risks. In conclusion, the risk of ischemic stroke is strongly increased shortly after the diagnosis of heart failure but returns to normal within 6 months after onset of heart failure.