This study introduces an enhanced feature selection method that is efficient in differentiating the malignant tumor patients from the benign patients by using K-Means clustering method combined with enhanced harmony search algorithm. The start of malignant tumor is caused by gene mutation process, it is very vital to identify and classify the presence or absence of the malignant tumor through analyzing the gene information. The planned methodology composed of four steps. The first step is to preprocess the original data by using min-max normalization. In the next step, generalized fisher score is used to find and eliminate the redundant data to confine the significant candidate genes. Selection of representative gene from each cluster is done by the K-Means clustering technique in the next phase. In the final phase the vital features for classification are selected by enhanced harmony search algorithm. The selected gene combination through this method for feature selection is then applied to the classification model and verified by means of 5-fold cross validation method. The projected model obtained a classification accuracy of up to 96.67%. Additionally, on comparing the projected method with other methods, the projected method performs well in classifying malignant tumor. This new method performs well in classification of brain tumors to malignant or benign. The projected model cannot be restricted only with the classification of brain tumors, but can also be used for other gene-related diseases effectively.