Depth of anesthesia is a matter of great importance in surgery. Determination of depth of anesthesia is a time consuming and difficult task carried out by experts. This study aims to decide a method that can classify EEG data automatically with a high accuracy and, so will help the experts for determination process. This study consists of three stages: feature extraction of EEG signals, feature selection, and classification. In the feature extraction stage, 41 feature parameters are obtained. Feature selection stage is important to eliminate redundant attributes and improve prediction accuracy and performance in terms of computational time. Effective feature selection algorithms such as minimum redundancy maximum relevance (mRMR); ReliefF; and Sequential Forward Selection (SFS) are preferred at the feature selection stage to select a set of features which best represent EEG signals. These obtained features are used as input parameters of the classification algorithms. At the classification stage, six different classification algorithms such as random forest (RF); feed-forward neural network (FFNN); C4.5 decision tree algorithm (C4.5); support vector machines (SVM); naive bayes; and radial basis function neural network (RBF) are preferred to classify the problem. A comparison is provided between computation times and accuracy rates of these different classification algorithms. The experimental results show that better results according to other classifiers when the obtained attributes by ReliefF algorithm are used with RF classifier.