The Web services classification is the process that automatically assigns a category from a list of predefined categories to the Web service described as a WSDL document and where the purpose is to improve the Web services discovery process speed. The aim of this paper is to propose an optimization approach based on the attributes selection of Web services descriptions, to automatically classify Web services found in UDDI registers in predefined categories. The proposed approach combines the meta-heuristic of Stochastic Local Search (SLS) with a supervised learning method. The purpose of this work is to optimize the classification rate of the classifier by choosing the relevant attributes that best represents the Web service. First, we propose a classification method that uses a stochastic local search (SLS) for the attributes selection, then, in a second phase, the approach calls for a supervised classification method to perform the classification task. To this end, we studied six well-known classifiers which are: Support Vector Machine (SVM), Naïve Bayes (NB), k -Nearest Neighbors ( k -NN), Bayesian Network (BN), Random Tree (RT), and Random Forests (RF). The six hybrid methods which are: SVM + SLS, NB + SLS, k -NN + SLS, BN + SLS, RT + SLS, and RF + SLS are evaluated on seven real datasets. The results are interesting and demonstrate the benefits of the proposed approaches for Web service classification.