Large margin classifiers, as support vector machines, have been widely used quite effectively on high dimensional problems. In this sense, it is important to develop new feature selection strategies that are associated with this type of classifier. In this work, we propose a new method for feature selection based on an ordered search process, also known as best-first, to explore the space of possible candidates. The algorithm, called AOS, uses as a search measure the margin values calculated using a large margin classifier. This highly efficient classifier allows great flexibility and speed in obtaining the margin values, enabling the solution of problems of reasonable size, with hundreds of features, and avoiding combinatorial explosion. The algorithm was tested on several problems from the literature and the results were compared to other methods. An important theoretical contribution of the paper refers to the concept of the projected margin. This value, computed as the projection of the maximal margin vector on a lower dimensional subspace, is used as an upper bound to the actual maximal margin. This enables greater efficiency and speed in solving problems of classification and, therefore, in the search process as a whole.