This study has aimed to develop a novel pre-diagnostic tool for primary care screening of heart disease based on multivariate short-term heart rate variability (HRV) analyzed by linear (time and frequency domain) and nonlinear methods (compression entropy (CE), detrended fluctuation analysis (DFA), Poincaré plot analysis, symbolic dynamics) applied to 5-min ECG segments. Firstly, we applied HRV analysis to separate healthy subjects (REF) from heart disease patients (PAT). Then to optimize the results, we subdivided both groups according to gender: REF (♂ = 78, ♀ = 53) versus PAT (♂ = 378, ♀ = 115). Finally, we divided REF and PAT into two age subgroups (30-50 years vs. 51-70 years of age) to consider the influence of age on HRV. Heart disease patients were classified using a scoring system based on cut-off values calculated from all HRV indices obtained from the REF. After combining the optimum indices from all different analyzing methods, sensitivities of more than 72% and a specificity of 100% in all subgroups were revealed. Nonlinear indices proved to be better for discriminating heart disease patients from healthy subjects. Multivariate short-term HRV, analyzed by both linear and nonlinear methods appears to be a suitable pre-diagnostic tool for screening heart disease in primary care settings.