Importance: Guidelines recommend that cardiac rehabilitation (CR) exercise training should not start until 6 weeks after sternotomy, although this is not evidence based. Limited data suggest that starting earlier is not detrimental, but clinical trials are needed. Objective: To compare the effectiveness and safety of CR exercise training started either 2 weeks (early CR) or 6 weeks (usual-care CR) after sternotomy. Design, Setting, and Participants: This was an assessor-blind, noninferiority, parallel-group, randomized clinical trial that conducted participant recruitment from June 12, 2017, to March 17, 2020. Participants were consecutive cardiac surgery sternotomy patients recruited from 2 outpatient National Health Service rehabilitation centers: University Hospital, Coventry, UK, and Hospital of St Cross, Rugby, UK. Interventions: Participants were randomly assigned to 8 weeks of twice-weekly supervised CR exercise training starting either 2 weeks (early CR) or 6 weeks (usual-care CR) after sternotomy. Exercise training adhered to existing guidelines, including functional strength and cardiovascular components. Main Outcomes and Measures: Outcomes were assessed at baseline (inpatient after surgery), after CR (10 or 14 weeks after sternotomy), and 12 months after randomization. The primary outcome was the change in 6-minute walk test distance from baseline to after CR. Secondary outcomes included safety, functional fitness, and quality of life. Results: A total of 158 participants (mean [SD] age, 63 [11.5] years, 133 male patients [84.2%]) were randomly assigned to study groups; 118 patients (usual-care CR, 61 [51.7%]; early CR, 57 [48.3%]) were included in the primary analysis. Early CR was not inferior to usual-care CR (noninferiority margin, 35 m); the mean change in 6-minute walk distance from baseline to after CR was 28 m greater in the early CR group (95% CI, -11 to 66; P =.16). Mean differences for secondary outcomes were not statistically significant, indicating noninferiority of early CR. There were 46 vs 58 adverse events and 14 vs 18 serious adverse events in usual-care CR and early CR, respectively. There was no difference between the groups in the likelihood of participants having an adverse or serious adverse event. Conclusions and Relevance: Starting exercise training from 2 weeks after sternotomy was as effective as starting 6 weeks after sternotomy for improving 6-minute walk distance. With appropriate precautions, clinicians and CR professionals can consider starting exercise training as early as 2 weeks after sternotomy. Trial Registration: ClinicalTrials.gov Identifier: NCT03223558.