Background: To assess the link between serum potassium (K{}^{+}) and all-cause mortality in hospitalized heart failure (HF) patients. Methods: Hospitalized HF patients (n = 3114) were analyzed at the Fuwai Hospital Heart Failure Center. Before discharge, HF patients were divided into four groups according to the K{}^{+} level quartiles: K{}^{+} \le3.96 mmol/L (Q1), 3.96 K{}^{+} \le 4.22 mmol/L (Q2), 4.22 K{}^{+} \le 4.52 mmol/L (Q3), and K{}^{+} >4.52 mmol/L (Q4). At 90 days, 2 years, and maximal follow-up, all-cause mortality was the primary outcome. Results: Patients with HF in the Q4 group had worse cardiac function, higher N-terminal pro-B-type natriuretic peptide levels, lower left ventricular ejection fractions and lower estimated glomerular filtration rates than patients in the Q2 group. In the multivariate-adjusted Cox analysis, the mortality assessed during the 90-day, 2-year, and maximal follow-up examinations increased in the Q4 group of HF patients but not in the Q1 and Q3 groups. The Q4 group had a 28% (hazard ratio [HR]: 1.28, 95% confidence interval [CI]: 1.09–1.49, p = 0.002) higher risk of all-cause mortality at maximum follow-up. Hypokalemia and hyperkalemia were linked to increased HF mortality risk at the 90-day, 2-year, and maximal follow-up periods. Conclusions: Serum K{}^{+} levels had a J-shaped association with all-cause mortality in HF patients. Both hypokalemia and a K{}^{+} level of >4.52 mmol/L were associated with increased all-cause mortality in the short term and long term, suggesting a narrow target K{}^{+} range in HF patients. Clinical Trial Registration: Unique Identifier: NCT02664818; URL: ClinicalTrials.gov.