In recent years rapid advancement of modern technologies has produced enormous and varied data which needs to be pre-processed before applying various machine learning techniques to gain valuable insight from the data. Feature Selection is an indispensable pre-processing step that helps to remove undesirable features which deteriorate the desired output from the various machine learning techniques. Further, it helps to wane the overall execution time. Metaheuristic algorithms have successfully applied as a wrapper approach for selecting those features which boost the overall outcome of machine learning techniques either in supervised or unsupervised form. The present work proposes a Modified Binary Jaya Optimization Algorithm as a wrapper for selecting the feature sub-set using K-NN as a classifier in a supervised Machine Learning task. In the proposed work, a unique initialization technique using Mutual information Coefficient as a Filter has been applied along with the Lévy Flight-based update mechanism, and a variable Mutation function is activated as the algorithm gets trapped in a locally optimal solution. The proposed work has been applied to ten significant benchmark classification datasets. The results show substantial improvement when compared with Binary Jaya Optimization Algorithm regarding average accuracy, precision, recall, F1-score, and feature size.