The identification of sleep stages is essential in the diagnostics of sleep disorders, among which obstructive sleep apnea (OSA) is one of the most prevalent. However, manual scoring of sleep stages is time-consuming, subjective, and costly. To overcome this shortcoming, we aimed to develop an accurate deep learning approach for automatic classification of sleep stages and to study the effect of OSA severity on the classification accuracy. Overnight polysomnographic recordings from a public dataset of healthy individuals (Sleep-EDF, n = 153) and from a clinical dataset (n = 891) of patients with suspected OSA were used to develop a combined convolutional and long short-term memory neural network. On the public dataset, the model achieved sleep staging accuracy of 83.7% (κ = 0.77) with a single frontal EEG channel and 83.9% (κ = 0.78) when supplemented with EOG. For the clinical dataset, the model achieved accuracies of 82.9% (κ = 0.77) and 83.8% (κ = 0.78) with a single EEG channel and two channels (EEG+EOG), respectively. The sleep staging accuracy decreased with increasing OSA severity. The single-channel accuracy ranged from 84.5% (κ = 0.79) for individuals without OSA diagnosis to 76.5% (κ = 0.68) for patients with severe OSA. In conclusion, deep learning enables automatic sleep staging for suspected OSA patients with high accuracy and expectedly, the accuracy decreased with increasing OSA severity. Furthermore, the accuracies achieved in the public dataset were superior to previously published state-of-the-art methods. Adding an EOG channel did not significantly increase the accuracy. The automatic, single-channel-based sleep staging could enable easy, accurate, and cost-efficient integration of EEG recording into diagnostic ambulatory recordings.