The medical diagnostic decision support system uses machine learning and data mining algorithms to detect and diagnose diseases. Several deaths can be avoided if the diseases are detected and cured in the early stages of infection. Feature selection is a major pre-processing method used to obtain the most significant features, thereby enhancing the data mining model's classification accuracy. This work proposes a new feature selection algorithm to perform feature selection as a multi-objective optimization problem. The minimization of classification error rate and minimization of the feature subset's cardinality are the two contradictory objectives that need to be optimized simultaneously. The proposed work is applied for five clinical datasets such as lung cancer, breast cancer, diabetes, fertility, and immunotherapy and the results are compared with existing techniques based on 6 other datasets. This work converts the real-valued Jaya Optimization Algorithm into binary space. It also handles premature convergence and sensitivity–specificity trade-off. The proposed algorithm's efficiency is assessed and analyzed based on average classification accuracy, sensitivity, specificity, number of features selected, percentage feature selection, and CPU computation time. The proposed algorithm improves the effectiveness of data mining based medical diagnostic decision support system.