Poor implementation and variable quality of cardiac rehabilitation (CR) for coronary heart disease (CHD) have been a global concern. This nationwide study aimed to clarify the implementation of and participation in CR among CHD patients and associated factors in Japan. We conducted a retrospective cohort study using data extracted from the National Database of Health Insurance Claims and Specific Health Checkups of Japan. Patients who underwent percutaneous coronary intervention (PCI) or coronary artery bypass grafting (CABG) in 2017-2018 were included. Aspects of CR were assessed in terms of (1) participation in exercise-based CR, (2) pharmacological education, and (3) nutritional education. Of 87,829 eligible patients, 32% had participated in exercise-based CR, with a mean program length of 40 ± 71 days. CABG was associated with higher CR participation compared to PCI (OR 10.2, 95% CI 9.6-10.8). Patients living in the Kyushu region were more likely to participate in CR (OR 2.59, 95% CI 2.39-2.81). Among patients who participated in CR, 92% received pharmacological education, whereas only 67% received nutritional education. In Japan, the implementation of CR for CHD is insufficient and involved varying personal, therapeutic, and geographical factors. CR implementation needs to be promoted in the future.