Computer-aided sleep monitoring system can effectively reduce the burden of experts in analyzing the large volume of electroencephalogram (EEG) recordings corresponding to sleep stages. In this paper, a new technique for automated classification of sleep stages based on iterative filtering of EEG signals is presented. In order to perform sleep stages classification, the EEG signals are decomposed using iterative filtering method. The modes obtained from iterative filtering of EEG signal can be considered as amplitude-modulated and frequency-modulated (AM-FM) components. The discrete energy separation algorithm (DESA) is applied to the modes to determine amplitude envelope and instantaneous frequency functions. The extracted amplitude envelope and instantaneous frequency functions have been used to compute Poincaré plot descriptors and statistical measures. The Poincaré plot descriptors and statistical measures are applied as input features for different classifiers in order to classify sleep stages. The classifiers namely, naïve Bayes, k-nearest neighbor, multilayer perceptron, C4.5 decision tree, and random forest are applied in order to classify the EEG epochs corresponding to various sleep stages. The experimental study has been performed on online available Sleep-EDF database for two-class to six-class classification of sleep stages based on EEG signals. The two-class to six-class classification problems are formulated by taking different combinations of EEG signals corresponding to various sleep stages. The comparison of the results is presented for different multi-class classification problems with the other recently proposed methods. The results show that the proposed method has provided better tenfold cross-validation classification accuracy than other existing methods.