Coronary artery disease (CAD) is a leading cause of death worldwide. Heart rate variability (HRV) has been proven to be a non-invasive marker of the autonomic modulation of the heart. Nonlinear analyses of HRV signals have shown that the HRV is reduced significantly in patients with CAD. Therefore, in this work, we extracted nonlinear features from the HRV signals using the following techniques: recurrence plots (RP), Poincare plots, and detrended fluctuation analysis (DFA). We also extracted three types of entropy, namely, Shannon entropy (ShanEn), approximation entropy (ApEn), and sample entropy (SampEn). These features were subjected to principal component analysis (PCA). The significant principal components were evaluated using eight classification techniques, and the performances of these techniques were evaluated to determine which presented the highest accuracy in classifying normal and CAD classes. We observed that the multilayer perceptron (MLP) method resulted in the highest classification accuracy (89.5%) using our proposed technique.