Heart failure (HF) diagnosis is complicated by varied pathophysiology, nonspecific symptoms and underlying comorbidities. This patient heterogeneity makes accurate treatment challenging and, as a result, can lead to worse clinical outcomes and increased healthcare cost. Measuring the plasma concentrations of natriuretic peptides can assist HF diagnosis with only moderate specificity. Therefore, there is a need for better diagnostic biomarkers with a higher specificity to establish the identification of HF, as well as to characterize and sub-profile HF patients for better treatment. We performed liquid chromatography mass spectrometry (LC-MS) to analyze the plasma proteomes of 249 HFpEF patients and 250 HFrEF patients (BIOSTAT-CHF) versus a control cohort of 99 patients without heart failure (PREVEND study). We identify significant changes in the plasma proteomes of HF patients versus non-HF controls. We applied machine learning algorithms to the data to identify new biomarker candidates for diagnosing HF and validated our findings in an independent heart failure cohort. Furthermore, we performed clustering analysis on the plasma protein profiles of the patients in order to characterize differences in HF sub-populations.