Increasing availability and popularity of cloud Storage as a Service (STaaS) offers alternatives to traditional on-line video entertainment models, which rely on expensive Content Delivery Networks (CDNs). In this paper, we present an elastic analytic solution model to ensure Quality of Service (QoS) when providing Video-on-Demand (VoD) using several third party elastic cloud storage services. First, we individually gather cloud storage start-up delays, and characterize them to show that they are heavy-tailed. Then, we perform a meta-characterization of these delays using Principal Component Analysis (PCA) to create a characteristic cloud delay trace. By using different estimation techniques of the Hurst Parameter, we demonstrate that this new trace (also heavy-tailed) exhibits self-similarity, a property not sufficiently studied in cloud storage environments. Finally, we pursue stochastic modeling using different heavy-tailed probability distributions to derive prediction models and elasticity parameters from the cloud VoD system. We obtain a stochastic self-similar model and compare it with trace based simulation results by testing different heavy-tailed probability distributions, meta-cloud elasticity values and Hurst parameters. Since our approach optimizes QoS, we guarantee a specific video start-up delay for a number of arriving clients. This is a strong commitment for a VoD service, because traditional cloud approaches often focus on a best-effort paradigm optimizing performance, cost, and bandwidth, among other parameters.