Due to the rapid development of Web technologies, Internet applications increasingly use different programming languages and platforms. Web services technologies were introduced to ease the integration of applications on heterogeneous platforms. The quality of Web services has received much attention as it relates to the service discovery process. However, less work has been done on issues related to the quality of composite services. This study uses the selection model along with the concept of workflow quality of service (QoS) in order to improve the quality of service performance of current Web services in the discovery process. It also uses a selection model as the foundation for selecting Web services, conducting simulations to measure the overall workflow QoS performance when implemented in sequence. However, optimal solutions to service composition selection require exponential time in the number of services. We therefore apply genetic algorithm to quickly find the best-fitting service composition. Finally, we score and sort each service composition based on the service requesters’ preferences towards QoS. The results of the experiment show that considering workflow QoS in selecting service composition improves the actual QoS performance. At the same time, using genetic algorithm to optimize the service composition provides an improvement in the solution time.