This study presents an effective disease-diagnosing technique using the machine learning algorithm on clinical datasets. Early identification and prediction of diseases can save valuable human lives. This paper introduces a novel approach named the Optimized-Weighted K-Nearest Neighbor (OWKNN) algorithm which enhances the traditional KNN for more accurate disease prediction. It leverages the Mutual Information (MI) score to determine the importance of the features and estimate Mahalanobis distance measure for distance weighting. The Genetic Algorithm has been employed to determine the optimal weights for both distance and feature importance. These weights are combined according to the GA optimum weights for weighted majority voting. The Dempster–Shafer Theory is utilized to aggregate evidence from multiple neighbors for decision-making under uncertainty for more accurate prediction of diseases. The proposed OWKNN method was tested on four real benchmark datasets. The efficiency of the proposed method is evaluated, and its performance was compared with traditional KNN and other popular classifiers such as Classification and Regression trees (CARTs), Artificial Neural Networks (ANNs), Support Vector Machine (SVM), Random Forest (RF), and Naïve Bayes (NB). Experimental results show that the proposed method consistently beats these algorithms in terms of average accuracy, precision, recall, and F1-score of 89.74%, 89%, 82.53%, and 84.08%, respectively, across various datasets. Thus, this work comes up with an improved version of the machine learning algorithm (KNN) for effective medical diagnostics.