Despite cardiac rehabilitation (CR) being a recommended treatment for patients with heart failure with reduced ejection fraction (HFrEF), it is still underused. This study investigated the clinical determinants and barriers to enrollment in a CR program for HFrEF patients. We conducted a cohort study using the Cardiac Rehabilitation Barriers Scale (CRBS) to assess the reason for non-enrollment. Of 214 HFrEF patients, 65% had not been enrolled in CR. Patients not enrolled in CR programs were older (63 vs. 58 years; p < 0.01) and were more likely to have chronic obstructive pulmonary disease (COPD) (20% vs. 5%; p < 0.01). Patients enrolled in CR were more likely to be treated with sacubitril/valsartan (34% vs. 19%; p = 0.01), mineralocorticoid receptor antagonists (84% vs. 72%; p = 0.04), an implantable cardioverter defibrillator (ICD) (41% vs. 20%; p < 0.01), and cardiac resynchronization therapy (21% vs. 10%; p = 0.03). Multivariate analysis revealed that age (adjusted OR 1.04; 95% CI 1.01−1.07), higher education level (adjusted OR 3.31; 95% CI 1.63−6.70), stroke (adjusted OR 3.29; 95% CI 1.06−10.27), COPD (adjusted OR 4.82; 95% CI 1.53−15.16), and no ICD status (adjusted OR 2.68; 95% CI 1.36−5.26) were independently associated with CR non-enrollment. The main reasons for not being enrolled in CR were no medical referral (31%), concomitant medical problems (28%), patient refusal (11%), and geographical distance to the hospital (9%). Despite the relatively high proportion (35%) of HFrEF patients who underwent CR, the enrollment rate can be further improved. Innovative multi-level strategies addressing physicians’ awareness, patients’ comorbidities, and geographical issues should be pursued.