Abstract: As the number of available Web services is steadily increasing, there is a growing interest for reusing basic Web services in new, composite Web services. However, most current Web services choreography proposals, such as BPEL4WS or WSCI, need a fixed execution flow previously designed by human, thus the adaptability of Web services can not be fully used. Through formalizing the description of single Web service, a Web services composition mechanism based on dependences between tasks is developed and a flexible and self-adaptable workflow model to compose Web services automatically is proposed. Furthermore, respective algorithms to verify the correctness of composition process are developed and a dynamic compensation mechanism is designed to handle exceptions, which adds considerable practicability to the workflow model.