Obstructive sleep apnea syndrome (OSAS) is a common sleep disorder that yields cardiovascular diseases, excessive daytime sleepiness, and poor quality of life if not treated. Classification of OSAS from electrocardiograms (ECGs) is a noninvasive method and much more affordable than traditional methods. This study proposes a pattern recognition system for automated apnea diagnosis based on heart rate variability (HRV) and ECG-derived respiratory signals. The k-nearest neighbor (k-NN) classifier has been used to develop the models for classifying the sleep apnea types. For comparison purposes, classification models based on multilayer perceptron, support vector machines, and C4.5 decision tree (C4.5 DT) have also been developed. The first database used for training contains 12 and the second used for testing contains 35 whole-night polysomnography recordings from real subjects. Wrapper-based feature selection, optimal parameter calculation, and 10-fold cross-validation were applied to the training dataset. The performance of the classifiers was evaluated by accuracy, sensitivity, and specificity metrics. The k-NN classifier yields higher classification accuracy, sensitivity, and specificity by successfully separating 100% of apnea recordings from normal recordings, and it also achieves a classification rate of 97% accuracy, 89% sensitivity, and 100% specificity of the subjects in the test database. Median, mean, absolute deviation, and interquartile range values of HRV were the most descriptive parameters. These results indicate significant potential for achieving basic estimates for OSAS patients.