Traditional service composition approaches are top-down(using domain knowledge to break-down the desired functionality), or bottom-up (using planning techniques). The former rely on available problem decomposition knowledge, whilst the latter rely on the availability of a known set of services, otherwise automatic composition has been considered impossible. We address this by proposing a third approach: Cooperative Service Composition (CSC),inspired by the way organisations come together in consortia to deliver services. CSC considers each service provider as proactive in service composition, and provides a semantics-based mechanism allowing innovative service compositions to emerge as result of providers' interactions. The key challenges we resolve are how to determine if a contribution brings the composition closer to its goal, and how to limit the number of possible solutions. In this paper we describe the approach and the solutions to the two key challenges, and demonstrate their application to the composition of financial web services. © 2012 Springer-Verlag Berlin Heidelberg.