Abstract Background and Aims Magnesium deficiency is associated with poor outcomes in patients with heart failure (HF), but less is known about the impact of oral magnesium therapy. This study aimed to examine the association of oral magnesium with outcomes in patients with HF and whether it depends on baseline serum magnesium. Methods Of 54 696 Veterans with HF (2001–2023) and hypomagnesemia (serum magnesium <1.7 mg/dL), 10 695 were initiated on oral magnesium (median dose, 420 mg/day). A propensity score-matched cohort of 21 098 patients (treated, n = 10 549) balanced on 71 baseline characteristics was assembled while remaining outcome-blinded. This process was repeated to assemble a matched cohort of 11 634 patients (treated, n = 5817) with normomagnesemia (serum magnesium, 1.7–2.3 mg/dL). Hazard ratios (HR) (95% confidence intervals [CIs]) for one-year outcomes associated with oral magnesium were estimated. Results In the hypomagnesemia cohort, HF hospitalization or death occurred in 21.7% of patients not receiving and 20.1% receiving oral magnesium (HR: 0.91; 95% CI: 0.86–0.97). Respective HRs (95% CIs) in subgroups with serum magnesium 1.6 (n = 5929), 1.3–1.5 (n = 11 293) and <1.3 (n = 3876) mg/dL were 0.99 (0.88–1.12), 0.91 (0.84–0.98; interaction P = .20), and 0.81 (0.71–0.93; interaction P = .03). Respective rates in the normomagnesemia cohort were 17.8% and 19.5% (HR: 1.11; 95% CI: 1.02–1.21). Spline regression analysis revealed that HRs were lower at serum magnesium <1.5 mg/dL, higher at >1.8 mg/dL, and not significant at 1.5–1.8 mg/dL. Conclusions Oral magnesium therapy was associated with a lower risk of HF hospitalization or death in patients with HF and hypomagnesemia. Future clinical trials need to confirm these findings.