Heart rate variability (HRV) has been shown to be attenuated in patients with coronary artery disease (CAD) and may, therefore, be possibly used for the early detection of myocardial ischemia. We aimed to evaluate the diagnostic yield of a novel short-term HRV algorithm for the detection of myocardial ischemia in subjects without known CAD. We prospectively enrolled 450 subjects without known CAD who were referred to tertiary medical centers for exercise stress testing (EST) with single-photon emission computed tomography myocardial perfusion imaging (MPI). All subjects underwent 1-hour Holter testing with subsequent HRV analysis before EST with MPI. The diagnostic yield of HRV analysis was compared with EST, using MPI as the gold standard for the noninvasive detection of myocardial ischemia. All subjects had intermediate pretest probability for CAD. Mean age was 62 years, 38% were women, 51% had hypertension, and 25% diabetes mellitus. HRV analysis showed superior sensitivity (77%) compared with standard EST (27%). After multivariate adjustment, HRV was independently associated with an 8.4-fold (p <0.001) increased likelihood for the detection of myocardial ischemia by MPI, whereas EST did not show a statistically significant association with a positive MPI (odds ratio 2.1; p = 0.12). Of subjects who were referred for subsequent coronary angiography, the respective sensitivities of HRV and EST for the detection of significant CAD were 73% versus 26%. Our data suggest that HRV can be used as an important noninvasive technique for the detection of myocardial ischemia in subjects without known CAD, providing superior sensitivity to conventional EST in this population.