This paper presents an approach to metaheuristic-based feature subset selection. Feature selection is an NP-problem. This means that finding the optimal feature set is an intractable problem. Approximate algorithms are very convenient since the exhaustive search is prohibitive due to the extremely high computational cost. Metaheuristics are a key approach in the field of data mining and especially in data pre-processing. Scatter search has been applied in context of feature selection although ant search is more widespread in the data preparation area. This contribution hybridises both search strategies to get a prediction model which is able to predict faster and more accurately with further unseen data. First the scatter search takes place and the reached solution is improved by means of an ant search. The test-bed comprises a good number of high-dimensional data sets. Results are very substantial since the second metaheuristic improves greatly the performance of the classifiers and reduces the models’ complexity in terms of input feature space.