Background: Few studies are published on heart failure patients in primary health care, in elderly in advanced age. Objective: The purpose of this study was to examine the accuracy of the diagnosis of heart failure in all men and women with focus on age and gender. Methods: The patients were recruited from one selected primary health care in the city of Skellefteå, Sweden. The general practitioners included all patients who had symptoms and signs indicating heart failure. The patients were then referred for an echocardiographic examination and a final cardiology consultation. Results: The general practitioners identified 121 women and 49 men with suspected heart failure of whom 39% (51 women and 16 men) were above 80 years. Women were significantly older than men (mean age 78 and 75 years, respectively, p = 0.03). The main symptom was dyspnoea (80%). Confirmed heart failure was verified in 45% of the patients and was significantly more common in men than women (p = 0.02). Of all men and women above 80 years, 75% and 22%, respectively (p = 0.01) had a verified systolic heart failure, while there were no significant gender differences in patients younger than 80. In a multivariate regression analysis taking gender, age, smoking, atrial fibrillation, hypertension, angina, myocardial infarction and diabetes into account, myocardial infarction (OR = 4.3, CL = 1.8–10.6) hypertension (OR = 3.4, CI = 1.6–6.9) atrial fibrillation (OR = 2.8, CL = 1.0–7.9) remained significantly predictive of a confirmed diagnosis of heart failure. Conclusion: This study showed the difficulty of diagnosing heart failure accurately based only on clinical symptoms, especially in women above 80 years.