One crucial key of developing an automatic sleep stage scoring method is to extract discriminative features. In this paper, we present a novel technique, termed common frequency pattern (CFP), to extract the variance features from a single-channel electroencephalogram (EEG) signal for sleep stage classification. The learning task is formulated by finding significant frequency patterns that maximize variance for one class and that at the same time, minimize variance for the other class. The proposed methodology for automated sleep scoring is tested on the benchmark Sleep-EDF database and finally achieves 97.9%, 94.22%, and 90.16% accuracy for two-state, three-state, and five-state classification of sleep stages. Experimental results demonstrate that the proposed method identifies discriminative characteristics of sleep stages robustly and achieves better performance as compared to the state-of-the-art sleep staging algorithms. Apart from the enhanced classification, the frequency patterns that are determined by the CFP algorithm is able to find the most significant bands of frequency for classification and could be helpful for a better understanding of the mechanisms of sleep stages.