Medical databases contain massive volume of clinical data which could provide valuable information regarding diagnosis, prognosis and treatment plan when mining algorithms are used in appropriate manner. The irrelevant, redundant and incomplete data in medical databases makes the extraction of useful pattern a difficult process. Feature selection, a robust data preprocessing method selects attributes that enhances the predictive accuracy of classification algorithms. Consistency subset evaluation with best first search approach selects a feature subset of consistence equal to that of full feature set. The optimal feature subset selected is classified using Modlem, a rough set based rule-induction algorithm. The performance of the classification algorithms are evaluated in terms of three metrics viz, Accuracy, Sensitivity and Specificity. © 2014 IEEE.