Human stress is a serious health concern, which must be addressed with appropriate actions for a healthy society. This paper presents an experimental study to ascertain the appropriate phase, when electroencephalography (EEG) based data should be recorded for classification of perceived mental stress. The process involves data acquisition, pre-processing, feature extraction and selection, and classification. The stress level of each subject is recorded by using a standard perceived stress scale questionnaire, which is then used to label the EEG data. The data are divided into two (stressed and non-stressed) and three (non-stressed, mildly stressed, and stressed) classes. The EEG data of 28 participants are recorded using a commercially available four channel Muse EEG headband in two phases i.e., pre-activity and post-activity. Five feature groups, which include power spectral density, correlation, differential asymmetry, rational asymmetry, and power spectrum are extracted from five bands of each EEG channel. We propose a new feature selection algorithm, which selects features from appropriate EEG frequency band based on classification accuracy. Three classifiers i.e., support vector machine, the Naive Bayes, and multi-layer perceptron are used to classify stress level of the participants. It is evident from our results that EEG recording during the pre-activity phase is better for classifying the perceived stress. An accuracy of and is achieved for two- and three-class stress classification, respectively, while utilizing five groups of features from theta band. Our proposed feature selection algorithm is compared with existing algorithms and gives better classification results.