Cloud-computing facilitates consumers to source online storage-services on a pay-as-you-go basis. The sourcing of storage-as-a-service (STaaS) requires a decision maker to contend with several elements such as pricing structure, application characteristics and quality-of-service requirements, in addition to tactical considerations such as risk propensity and supplier diversification. This makes STaaS sourcing a complex task. Discussion on STaaS sourcing models addressing these aspects and their utility to decision-makers is, however, scant. In this paper, we propose a two-stage holistic approach based on Data Envelopment Analysis (DEA) and Goal programming (GP). We derive insights provided by these models from 10800 runs using market-based data. We also use an experiment to assess our hypothesis concerning the impact of task complexity on decision-quality. Both these experiments have implications for different business scenarios in the STaaS market, and for decision-making. We discuss these managerial implications, and present a prototype Decision Support System (DSS) to aid STaaS selection. © 2015, Springer Science+Business Media New York.