The clinical relevance of polyunsaturated fatty acids (PUFAs) in heart failure remains unclear. The aim of this study was to investigate the association between PUFA levels and the prognosis of patients with heart failure with preserved ejection fraction (HFpEF). This retrospective study included 140 hospitalized patients with acute decompensated HFpEF (median age 84.0 years, 42.9% men). The patients’ nutritional status was assessed, using the geriatric nutritional risk index (GNRI), and their plasma levels of eicosapentaenoic acid (EPA), docosahexaenoic acid (DHA), arachidonic acid (AA), and dihomo-gamma-linolenic acid (DGLA) were measured before discharge. The primary outcome was all-cause mortality. During a median follow-up of 23.3 months, the primary outcome occurred in 37 patients (26.4%). A Kaplan–Meier analysis showed that lower DHA and DGLA levels, but not EPA or AA levels, were significantly associated with an increase in all-cause death (log-rank; p < 0.001 and p = 0.040, respectively). A multivariate Cox regression analysis also revealed that DHA levels were significantly associated with the incidence of all-cause death (HR: 0.16, 95% CI: 0.06–0.44, p = 0.001), independent of the GNRI. Our results suggest that low plasma DHA levels may be a useful predictor of all-cause mortality and potential therapeutic target in patients with acute decompensated HFpEF.