Feature selection is an important step regarding Electroencephalogram (EEG) classification, for a Brain-Computer Interface (BCI) systems, related to Motor Imagery (MI), due to large amount of features, and few samples. This makes the classification process computationally expensive, and limits the BCI systems real-time applicability. One solution to this problem, is to introduce a feature selection step, to reduce the number of features before classification. The problem that needs to be solved, is that by reducing the number of features, the classification accuracy suffers. Many studies propose Genetic Algorithms (GA), as solutions for feature selection problems, with Non-Dominated Sorting Genetic Algorithm II (NSGA-II) being one of the most widely used GAs in this regard. There are many different configurations applicable to GAs, specifically different combinations of individual representations, breeding operators, and objective functions. This study evaluates different combinations of representations, selection, and crossover operators, to see how different combinations perform regarding accuracy, and feature reduction, for EEG classification relating to MI. In total, 24 NSGA-II combinations were evaluated, combined with three different objective functions, on six subjects. Results shows that the breeding operators have little impact on both the average accuracy, and feature reduction. However, the individual representation, and objective function does, with a hierarchical, and an integer-based representation, achieved the most promising results regarding representations, while Pearson’s Correlation Feature Selection, combined with k-Nearest Neighbors, or Feature Reduction, obtained the most significant results regarding objective functions. These combinations were evaluated with five classifiers, where Linear Discriminant Analysis, Support Vector Machine (linear kernel), and Artificial Neural Network produced the highest, and most consistent accuracies. These results can help future studies develop their GAs, and selecting classifiers, regarding feature selection, in EEG-based MI classification, for BCI systems.