Low hemoglobin (Hb) levels are attracting interest as a risk factor for cognitive impairment, but with contrasting evidence emerging from the current literature. The aim of our work was to investigate the relationship between baseline serum Hb levels and the incidence of cognitive impairment in older people over a follow-up of 4.4 years. Our study considered a sample of 1227 elderly subjects cognitively intact at baseline, enrolled under the Progetto Veneto Anziani (Pro.V.A.) among 3099 screened subjects. For all participants, we measured serum Hb levels on blood samples; incident cognitive impairment was defined as a Mini Mental State Examination (MMSE) score <24 and confirmed by geriatricians skilled in psychogeriatric medicine. No differences in baseline MMSE scores across Hb tertiles emerged in either gender. After the 4.4 years of follow-up, we identified 403 new cases of cognitive impairment (147 men and 256 women). Cox's regression analysis showed that participants with the lowest baseline Hb concentrations carried a significant 37% higher risk (95% confidence interval [CI]: 1.08-1.75; p = 0.01) of being diagnosed with cognitive impairment during the follow-up. Considering the gender separately, the risk of cognitive impairment only increased significantly, by 60%, for men in the lowest Hb tertile (95% CI: 1.06-2.41; p = 0.02), but not for women (hazard ratio = 1.32; 95% CI: 0.97-1.79; p = 0.08). In conclusion, low Hb concentrations may predict the onset of cognitive impairment in the elderly, apparently with a stronger association in men than in women.