Coronary artery disease (CAD) is one of the dangerous cardiac disease, often may lead to sudden cardiac death. It is difficult to diagnose CAD by manual inspection of electrocardiogram (ECG) signals. To automate this detection task, in this study, we extracted the heart rate (HR) from the ECG signals and used them as base signal for further analysis. We then analyzed the HR signals of both normal and CAD subjects using (i) time domain, (ii) frequency domain and (iii) nonlinear techniques. The following are the nonlinear methods that were used in this work: Poincare plots, Recurrence Quantification Analysis (RQA) parameters, Shannon entropy, Approximate Entropy (ApEn), Sample Entropy (SampEn), Higher Order Spectra (HOS) methods, Detrended Fluctuation Analysis (DFA), Empirical Mode Decomposition (EMD), Cumulants, and Correlation Dimension. As a result of the analysis, we present unique recurrence, Poincare and HOS plots for normal and CAD subjects. We have also observed significant variations in the range of these features with respect to normal and CAD classes, and have presented the same in this paper. We found that the RQA parameters were higher for CAD subjects indicating more rhythm. Since the activity of CAD subjects is less, similar signal patterns repeat more frequently compared to the normal subjects. The entropy based parameters, ApEn and SampEn, are lower for CAD subjects indicating lower entropy (less activity due to impairment) for CAD. Almost all HOS parameters showed higher values for the CAD group, indicating the presence of higher frequency content in the CAD signals. Thus, our study provides a deep insight into how such nonlinear features could be exploited to effectively and reliably detect the presence of CAD.