Obstructive Sleep Apnea Syndrome (OSAS) and Major Depressive Disorder (MDD) are both common conditions associated with poor quality of life. In this work, we seek to classify OSAS and depression in OSAS patients using multiple machine learning techniques. We have extracted features from 5-minute intervals selected from electrocardiograms (ECG), breathing signals, and electroencephalograms (EEG) recorded from a total of 118 subjects, of which 89 are used for training and 10-fold cross-validation and 29 are used for testing or a 75/25% split. This dataset was used as the input to three classification problems: sleep staging, classifying OSAS, and depression in OSAS patients. The best classification performance of OSAS was obtained with light sleep and deep sleep with the ReliefF feature selection algorithm using random forest and boosted trees for classification, respectively. It has yielded an accuracy of 100.00%, F1-Score of 100.00%, Cohen's κ Coefficient of 1.00, and a Matthews correlation coefficient (MCC) of 1.00. All sleep stages with 10 principal components following principal component analysis (PCA) and using random forest for classification yielded an accuracy of 77.50%, F1-Score of 78.05%, Cohen's κ of 0.571, and an MCC of 0.632 for classification of depression in OSAS patients. Sleep staging was best done using bagged trees with features selected via sequential backward feature selection, yielding an accuracy of 76.90%, F1-Score of 75.90%, Cohen's κ of 0.480, and an MCC of 0.634. These results show promise in detecting OSAS and depression in OSAS patients, particularly using labeled sleep stage data, light, and deep sleep.