A novel method for the automatic diagnosis of obstructive sleep apnea (OSA) from an electrocardiogram (ECG) is presented. This method aims to detect OSA utilizing exclusively ECG recordings during sleep and present a minute-by-minute signal processing technique. In the proposed algorithm, a wide range of features based on heart rate variability (HRV) and ECG-derived respiratory (EDR) signals are considered. The novelty of this study arises from employing bispectral analysis to the HRV and EDR signals in order to illustrate quadratic phase-coupling that can be observed among signal components with different frequencies. From this perspective, in the proposed algorithm, a new feature set based on a higher order spectrum of HRV and EDR signals is introduced and it is utilized to extract information regarding their non-linearity and non-Gaussianity. This feature vector is then fed into the input of a least-square support vector machine classifier. To implement the proposed method, the apnea-ECG database, which contains 70 nocturnal ECG records gathered from volunteer men and women, is used in this work. Results obtained from cross-validating 35 data records show that the normal recordings could be separated from the apneic recordings with an accuracy of 95.57% and a sensitivity and specificity of 98.64% and 92.51%, respectively. In addition, 35 other records were used for a pure independent validation of the proposed method and the obtained accuracy, sensitivity and specificity was 94.12%, 93.46% and 94.79% respectively in OSA episode detection. The performance of our proposed technique is better than in other existing approaches. It can be used as a reliable tool for automatic OSA identification and as a result, it will improve medical services.