Feature selection (FS) determines the beneficial features in data and decreases the disadvantages of the curse of dimensionality. This work proposes a novel adaptive memetic binary optimization (AMBO) algoraaithm for FS. FS is an NP-Hard binary optimization problem. AMBO is a pure binary optimization algorithm that works in binary discrete search space. New candidate individuals are adaptively created by a single point, double point, uniform crossovers, and canonical mutation mechanism. Local improvement for the best and worst individuals is provided with a new binary logic-gate based memetic smart local search mechanism. The balance between exploration and exploitation is achieved by adaptively. A diverse dimension dataset experimental setup is provided for determining the success of the proposed method. AMBO firstly was compared with binary particle swarm optimization (BPSO), a genetic algorithm with a random wheel selection strategy (GARW), a genetic algorithm with a tournaments selection strategy (GATS), and a genetic algorithm with a random selection strategy (GARS). AMBO outperformed the opponents on 11 datasets, especially the largest one. Wilcoxon signed-rank test and Friedman’s test were conducted to show the statistical significance of AMBO. For an additional experiment with state-of-art metaheuristic algorithms in the literature, Population reduction binary gaining sharing knowledge-based algorithm with V-4 shaped transfer function (PbGSK-V4), binary salp swarm algorithm (BSSA), binary differential evolution algorithm (BDE), binary dragonfly algorithm (BDA), binary particle swarm optimization algorithm (BPSO), binary bat algorithm (BBA), binary ant lion optimization (BALO) and binary grey wolf optimizer (BGWO) are used in experiments with 21 datasets. The experimental results of the proposed AMBO algorithm are significantly better than the state-of-art algorithms, in terms of classification error rate, fitness function, and average selected features.