We aimed to evaluate the risk of coronary heart disease (CHD) according to dental caries status in middle-aged patients using a population-based cohort database containing medical/dental claims, health examination, and death records in the Republic of Korea. A total of 234,597 patients were identified in the database who were without history of cardiovascular disease, including 104,638 patients without dental caries, 41,696 with incipient/moderate stage dental caries, and 88,262 advanced/severe dental caries. We used Cox proportional hazards model adjusted for sociodemographic, lifestyle, and medical characteristics to compute hazard ratio (HR) and 95% confidence intervals (95% CI) for CHD according to severity of dental caries. During 1,491,190 person-years of follow-up, there were a total of 6,015 CHD events. After adjustment for potential confounders, patients in the highest quartile of outpatient visits for advanced/severe stage dental caries was associated with an increase in CHD risk (HR = 1.13; 95% CI: 1.04–1.22) as compared with patients without dental caries. When the analysis was restricted to the patients with advanced/severe dental caries, dose-response relationship between number of outpatient visits for dental caries and risk of CHD was observed (Ptrend: <0.001). Prevention and control of dental caries might be worth promoting in clinical practice to prevent CHD.