The use of cloud-based storage systems for storing data is a popular alternative to local storage systems. Beside several benefits of cloud-based storages, there are also downsides like vendor lock-in or unavailability. Moreover, the selection of the best fitting storage solution can be a tedious and cumbersome task and the storage requirements may change over time. In this paper, we formulate a system model that uses multiple cloud-based services to realize a redundant and cost-efficient storage. Within this system model, we formulate a local and a global optimization problem that considers historical data access information and predefined quality of service requirements to select a cost-efficient storage solution. Furthermore, we present a heuristic optimization approach for the global optimization. Extensive evaluations show the benefits of our work in comparison with a baseline that follows a state-of-the-art approach. We show that our solutions save up to 30% of the cumulative cost in comparison with the baseline.