Background Beta-blockers improve outcomes in patients with systolic heart failure. However, it is unknown whether their initial negative inotropic effect may increase 30-day all-cause readmission, a target outcome for Medicare cost reduction and financial penalty for hospitals under the Affordable Care Act. Methods Of the 3067 Medicare beneficiaries discharged alive from 106 Alabama hospitals (1998-2001) with a primary discharge diagnosis of heart failure and ejection fraction <45%, 2202 were not previously on beta-blocker therapy, of which 383 received new discharge prescriptions for beta-blockers. Propensity scores for beta-blocker use, estimated for each of the 2202 patients, were used to assemble a matched cohort of 380 pairs of patients receiving and not receiving beta-blockers who were balanced on 36 baseline characteristics (mean age 73 years, mean ejection fraction 27%, 45% women, 33% African American). Results Beta-blocker use was not associated with 30-day all-cause readmission (hazard ratio [HR] 0.87; 95% confidence interval [CI], 0.64-1.18) or heart failure readmission (HR 0.95; 95% CI, 0.57-1.58), but was significantly associated with lower 30-day all-cause mortality (HR 0.29; 95% CI, 0.12-0.73). During 4-year postdischarge, those in the beta-blocker group had lower mortality (HR 0.81; 95% CI, 0.67-0.98) and combined outcome of all-cause mortality or all-cause readmission (HR 0.87; 95% CI, 0.74-0.97), but not with all-cause readmission (HR 0.89; 95% CI, 0.76-1.04). Conclusions Among hospitalized older patients with systolic heart failure, discharge prescription of beta-blockers was associated with lower 30-day all-cause mortality and 4-year combined death or readmission outcomes without higher 30-day readmission.