In this paper, we propose an approach for the recovery of service abstractions out of sets of available services that play the role of alternative design-decisions, which can be used in a service-oriented application. A service abstraction pro- vides a uniform interface that hides dierences in the inter- faces of alternative services and consequently allows reduc- ing the coupling between the application and the services. To this end, we formally define the notion of service abstrac- tion and propose a hierarchical clustering algorithm that in- crementally recovers a hierarchy of service abstractions out of a given set of alternative design-decisions/services. Fi- nally, we evaluate the proposed algorithm with real-world sets of services and report on our findings.