Web service compositions have attracted considerable efforts in the context of supporting enterprise application integrations. For a composite service, in addition to its functional requirements, QoS requirements are important and deserve a special attention. The central question to a QoS composition problem is how to compose a service from different subcomponent services so that its overall QoS can satisfy certain requirements. In this paper, we propose an agent-based method using Fuzzy Distributed Constraint Satisfaction Problem (Fuzzy DisCSP) techniques to solve this problem. We show that by using the composition structures, local constraints can be constructed and used with DisCSP. We also present an a new algorithm called the Fuzzy constraint satisfaction Algorithm for Distributed Environment (FADE) to solve the problem and discuss our experiment in building a prototypical system to prove the feasibility of our approach.