As the population of the Internet users increases, various Web services, which are based on a set of standardized technologies, are now offered through the Internet. However, as the market becomes more competitive, atomic Web services are not sophisticated enough to meet users¡¦ needs, and the concept of Web services-based workflow emerges accordingly. Web services-based workflow is a workflow composed of several related activities, aiming to achieve certain task, and for each activity, there can be a set of candidate Web services to be selected. The goal is to make a selection, which optimizes the QoS of the entire workflow. Although numerous methods are proposed to solve this QoS-based Web services selection problem, most of them are based on a static QoS model, which cannot accurately reflect the real QoS measures, and as a result, methods based on this static model will not necessarily derive the optimal solution even in the average case. Therefore, in this thesis, we adopt a probability-based model, which represents QoS measures as probability mass functions, and propose a branch and bound algorithm for selecting Web services from a set of candidate Web services. Under this QoS model, the goal is to maximize the probability of meeting the QoS goal subject to some QoS constraints. As demonstrated by the results of our experiments, it is much more probable for a workflow to meets the QoS goal by executing the selection derived by the probability-based approach.