Abstract: In order to improve the efficiency of finding the optimal solution for web services composition problem to meet increasingly sophisticated demand of users, an algorithm called Particle-Ant Colony Algorithm (PACA) based on Quality of Service (QoS) is proposed in this article. This algorithm converts the web services composition problem into shortest path problem of QoS-based directed acyclic graph. First, find several suboptimal paths by Particle Swarm Optimization Algorithm (PSOA) and initialize the pheromones of these paths, then find optimal solution by Ant Colony Optimization Algorithm (ACOA). The experiment result indicates that the PACA can effectively improve the capability of optimizing web services composition problem. The results of the research has theoretical and practical reference values to relevant issues.