Background Acute decompensated heart failure (ADHF) is a leading cause of hospitalization in older persons in the United States. Reduced physical function and frailty are major determinants of adverse outcomes in older patients with hospitalized ADHF. However, these are not addressed by current heart failure (HF) management strategies and there has been little study of exercise training in older, frail HF patients with recent ADHF. Hypothesis Targeting physical frailty with a multi-domain structured physical rehabilitation intervention will improve physical function and reduce adverse outcomes among older patients experiencing a HF hospitalization. Study design REHAB-HF is a multi-center clinical trial in which 360 patients ≥60 years hospitalized with ADHF will be randomized either to a novel 12-week multi-domain physical rehabilitation intervention or to attention control. The goal of the intervention is to improve balance, mobility, strength and endurance utilizing reproducible, targeted exercises administered by a multi-disciplinary team with specific milestones for progression. The primary study aim is to assess the efficacy of the REHAB-HF intervention on physical function measured by total Short Physical Performance Battery score. The secondary outcome is 6-month all-cause rehospitalization. Additional outcome measures include quality of life and costs. Conclusions REHAB-HF is the first randomized trial of a physical function intervention in older patients with hospitalized ADHF designed to determine if addressing deficits in balance, mobility, strength and endurance improves physical function and reduces rehospitalizations. It will address key evidence gaps concerning the role of physical rehabilitation in the care of older patients, those with ADHF, frailty, and multiple comorbidities.