Service-oriented architectures enable an environment where businesses can expose services for use by their collaborators and their peer organizations. In such an environment, organizations may have long-standing cooperative agreements representing the existing services that they share. Furthermore, they may have service level agreements (SLAs) that assure the quality of service standards of the existing services. In an ad-hoc workflow scenario, a business may need to perform real-time composition of the existing services in response to consumer requests. In this work, we suggest that, in parallel to traditional web service composition, the business must also compose the corresponding SLAs of the chosen services to generate a guaranteed service level to the consumer. In this paper, we introduce a process for composing SLAs associated with a workflow of web services. This process results in the discovery of the best composite (i.e. workflow) capability while optimizing the underlying service-level attributes.