Abstract: Aiming to solve the distributed BPEL engine placing problem in cloud, a K-means based distributed BPEL engine placing algorithm was proposed. The algorithm transforms the BPEL engine placing model into some optimization model in mathematics, and the optimization problem is solved by K-means algorithm. How to apply the algorithm in different network topologies was also discussed, such as random graph and tree network. In the end, statistical software R was used as experiment tool to evaluate the algorithm. Results show that the proposed method can provide a more optimized bandwidth usage of combined BPEL service execution.