With the growing number of available Web Services, it is an imperative task to study how to compose Web Services based on the requirements of the customers, which is the main focus of this paper. The proposed method automatically composes Web Services directly according to the customers’ requirements, and then executes the composed services to achieve the customers’ goals. Based on the historic records of Web Services compositions, this method uses a heuristic approach to adjust the composition scheme. Experimental results show that the method is well fits for the volatile environment and yields better performance over other algorithms.