Abstract: The features that describe the training instances are crucial for the success of a machine learning (ML) algorithm. A training set described by redundant or irrelevant features, for instance, can mislead the ML algorithm into learning a poor expression of the real concept embedded in the data. Feature subset selection (FSS) processes invest in identifying and removing as much irrelevant and redundant information as possible. FSS processes generally conduct a heuristic search in the search space defined by all possible subsets of the initial feature set trying to identify the most relevant for the learning task. This paper describes an empirical investigation of the influence of the search mechanism in identifying a suitable feature subset, by comparatively evaluating five search methods, namely Hill-Climbing, Beam-Search, Random-Bit-Climber, Las Vegas search and Genetic Algorithm, combined with different strategies for initiating the process. Experiments were conducted using eleven knowledge domains and eleven different combinations of search-method/strategy. Results are presented and comparatively analyzed.