Service Composition enables a new way to create new services by assembling independent service components. One of the important goals in service composition is load balancing across service replicas. In this paper, a novel adaptive distributed load capacity based (LCB) algorithm is presented to solve the load balancing problem in service composition. LCB algorithm uses service routing mechanism to search services and transfer the application data. By self-adaptively calculating the load capacity (LC) metric, LCB algorithm can choose a reasonable service path. LC metric reflects the workload of the service node, and is adaptively adjusted according to the variations of the server’s load. Compared with the previous researches, LCB algorithm needn’t the global topology information and load information. It is much suitable for dynamic service composition in distributed systems. Simulations show that LCB algorithm performs well in terms of load balancing across the service replicas.