In practice, classification problems have appeared in many scientific fields, including finance, medicine and industry. It is critically important to develop an effective and accurate classification model. Although numerous useful classifiers have been proposed, they are unstable, sensitive to noise and slow in computation. To overcome these drawbacks, the combination of feature selection techniques with traditional machine learning models is of great help. In this paper, a novel feature selection method called the opposition-based seagull optimization algorithm (OSOA) is proposed and studied. The OSOA is constructed based on an SOA whose population is determined by the opposition-based learning (OBL) algorithm. To evaluate its overall classification performance, some measures, including classification accuracy, number of selected features, receiver operating characteristic curve (ROC), and computation time, are adopted. The empirical results indicate that the suggested method exhibits higher or similar accuracy and computational efficiency in comparison with genetic algorithm (GA)-, simulated annealing (SA)-, and Fisher score (FS)-based classification models. The experimental results show that the OSOA is a computationally efficient feature selection technique that has the ability to select relevant variables. Furthermore, it performs well with high-dimensional data whose number of variables exceeds the number of samples. Thus, the OSOA is an effective approach for the enhancement of classification performance.