Patients with heart failure (HF) are sometimes classified as malnourished, but the prognostic value of nutritional status in acute HF (AHF) remains largely unstudied. 1214 patients who were admitted to the intensive care unit between January 2000 and June 2016 were screened based on their serum albumin, lymphocyte count, and total cholesterol measures. A total of 458 HF patients were enrolled in this study. The Prognostic Nutritional Index (PNI) is calculated as 10 × serum albumin (g/dL) + 0.005 × lymphocyte count (per mm³) (lower = worse). The Controlling Nutritional Status (CONUT) score is points based, and is calculated using serum albumin, total cholesterol, and lymphocyte count (range 0–12, higher = worse). Patients were divided into three groups according to PNI: high-PNI (PNI < 35, n = 331), middle-PNI (35 ≤ PNI < 38, n = 50), and low-PNI (PNI ≥ 38, n = 77). They were also divided into four groups according to CONUT score: normal-CONUT (0–1, n = 128), mild-CONUT (2–4, n = 179), moderate-CONUT (5–8, n = 127), and severe-CONUT (≥9, n = 24). The PNI, which exhibited a good balance between sensitivity and specificity for predicting in-hospital mortality [66.1 and 68.4%, respectively; area under the curve (AUC) 0.716; 95% confidence interval (CI) 0.638–0.793), was 39.7 overall, while the CONUT score was 5 overall (61.4 and 68.4%, respectively; AUC 0.697; 95% CI 0.618–0.775). A Kaplan–Meier curve indicated that the prognosis, including all-cause death, was significantly (p < 0.001) poorer in low-PNI patients than in high-PNI groups and was also significantly poorer in severe-CONUT patients than in normal-CONUT and mild-CONUT groups. A multivariate Cox regression model showed that the low-PNI and severe-CONUT categories were independent predictors of 365-day mortality [hazard ratio (HR) 2.060, 95% CI 1.302–3.259 and HR 2.238, 95% CI 1.050–4.772, respectively). Malnutrition, as assessed using both the PNI and the CONUT score, has a prognostic impact in patients with severely decompensated AHF.