Malnutrition and systemic inflammation are associated with poor outcomes in patients with heart failure. Recent studies have reported that the advanced lung cancer inflammation index (ALI), derived from the body mass index (BMI), serum albumin level, and neutrophil-to-lymphocyte ratio (NLR), is associated with poor prognosis in several types of cancers. Each marker is also known to prognostic factor of heart failure. Therefore, we hypothesized that ALI may be useful for determining the prognosis of patients with acute decompensated heart failure (ADHF). We reviewed survival in 381 consecutive patients (age, 73.1 ± 11.4 years, 59% men) who were hospitalized for ADHF and discharged. ALI at discharge, calculated as BMI × albumin level/NLR, was used to divide the patients into tertiles (ALI < 23.88, 23.88 ≤ ALI < 42.43, and ALI ≥ 42.43). The patients were also stratified into six groups according to the ALI tertiles and median concentration (177 pg/mL) of brain natriuretic peptide (BNP). The primary endpoint comprised all-cause mortality and readmission because of heart failure. The median follow-up duration was 363 days (interquartile range: 147–721 days), and 166 patients (44%) experienced the primary endpoint. Kaplan–Meier analysis showed that the event rate decreased progressively from the first to the third ALI tertile (52%, 48%, and 31%, respectively; p = 0.0013). In a multivariate Cox proportional hazards model, the first tertile was an independent prognostic factor for the primary endpoint (third vs. first tertile: hazard ratio, 0.57; 95% confidence interval, 0.34–0.95; p = 0.031). The hazard ratio for the primary endpoint for the patients with high BNP and first tertile ALI relative to the patients with low BNP and third tertile ALI was 5.3 (95% confidence interval, 2.9–9.5; p < 0.001). ALI at discharge, a novel and simple index of nutrition and inflammation, may be useful for risk stratification and predicting the prognosis of patients with ADHF.