Service matching is a principal process of Web services discovery. Nowadays, the narrow concept of the atomic Web service matching, the high time complexity of the current matching algorithm and the difficult expression of the Web service matching for the intelligent optimization algorithms become the main problems in Web service matching development. To solve the above problems, this article introduces the concept of the compound service matching by extending the concept of the atomic service matching, and abstracts the mathematical expression of the compound matching problem by the fitness function and restriction. The expression of the solution of the Web service matching for the intelligent optimization algorithm is also proposed. Based on the co-evolutionary idea of particle swarm optimization (PSO) and simulated annealing (SA), the study puts forward a co-evolutionary algorithm (PSO-SA) to the compound Web service matching problem. According to the experimental results, PSO-SA achieves better matching precision than other optimization algorithms within the limit iterations on various dimensional matching problems. Also, PSO-SA shows the adaptive ability to the compound service matching and improves the quality of result of Web services discovery.