Web services have emerged as a popular technology for integrating distributed applications. A Web service composition is a description of how different Web services can interoperate in order to perform more complex tasks. QoS for composite Web services has attracted interests from both research and industrial communities. In this paper, we propose an agent-based solution for the QoS composition problem using Distributed Constraint Satisfaction Problem (DisCSP) techniques. We show that by using the composition structures, local constraints can be constructed and used with DisCSP. We also present an enhancement of the Asynchronous Aggregate Search (AAS) algorithm to solve the problem and discuss our initial experiment in building a multi-agent system to prove the feasibility of our approach.