The neutrophil-to-lymphocyte ratio (NLR) and red blood cell distribution width (RDW) are important indicators of adverse outcomes and have predictive value for many diseases; however, the relationships between frailty, and the NLR and RDW in patients with coronary heart disease (CHD) have not been determined. In this cross-sectional study, we investigated the association between frailty, and the NLR and RDW in elderly CHD patients ≥ 60 years of age. Frailty was defined according to frailty phenotype. Of 345 patients enrolled in the study, 22.6%, 58.3%, and 19.1% were characterized as robust, pre-frail, and frail, respectively. A significant positive correlation was observed between frailty and the NLR (r = 0.169) and RDW (r = 0.196). After adjusting for confounders, linear regression analyses showed that participants in the 4th quartile of the NLR or RDW were more likely to have a higher frailty phenotype score. Based on multivariable logistic regression, patients in the 4th quartile of the NLR and RDW, the fully-adjusted odds ratios for incident frailty were 2.894 (p = 0.011) and 2.494 (p = 0.040), respectively. Our findings indicate that frailty is associated with the NLR and RDW in elderly patients with CHD.