The need to create and deploy business application systems rapidly has sparked interest in using web services to compose them. When creating mission-critical business applications through web service compositions, in addition to ensuring that functional requirements are met, designers need to consider the end-to-end reliability, security, performance, and overall cost of the application. As the number of available coarse-grain business services grows, the problem of selecting appropriate services quickly becomes combinatorially explosive for realistic-sized business applications. This article develops a business-process-driven approach for composing service-oriented applications. We use a combination of weights to explore the entire QoS criteria landscape through the use of a multi-criteria genetic algorithm (GA) to identify a Pareto-optimal multidimensional frontier that permits managers to trade off conflicting objectives when selecting a set of services. We illustrate the effectiveness of the approach by applying it to a real-world drop-ship business application and compare its performance to another GA-based approach for service composition.