Background: Heart rate recovery (HRR) and chronotropic response to exercise (CR) each have prognostic value among patients undergoing exercise treadmill testing (ETT). However, little is known about their prognostic use in combination and in addition to the Duke Treadmill Score (DTS). Methods: We studied 9,519 outpatients undergoing ETT between 2001 and 2004. Patients were categorized by HRR and CR. The primary outcome was all-cause mortality or nonfatal myocardial infarction (MI). Cox proportional hazards modeling was used to control for demographics, clinical history, and DTS. Results: After multivariable adjustment for DTS and other demographic and clinical variables, patients with abnormal HRR and CR had higher rates of all-cause mortality or nonfatal MI, as compared to patients with normal HRR and CR (hazard ratio [HR] = 1.90, 95% CI 1.35-2.69). Addition of the HRR and CR to the DTS improved outcome prediction (c-statistic improved from 0.61 to 0.68). Low-risk DTS patients with abnormal HRR and CR had significantly higher rates of all-cause mortality or nonfatal MI (HR 2.59, 95% CI 1.55-4.32), compared to low-risk DTS patients with normal HRR and CR. Conclusions: Abnormal HRR and CR identified ETT patients with higher rates of all-cause mortality or nonfatal MI and provided additional risk stratification among low-risk DTS patients. These results support the routine incorporation of HRR and CR in ETT reporting and suggest the need to evaluate whether further testing and/or more intensive treatment of these higher risk patients can improve outcomes.