Deployment mechanisms in Cloud environments are becoming more and more attractive to developers that find them easy and convenient to deploy their applications in just few steps. These mechanisms reduced the development cycles from weeks to hours. In this context, elasticity plays an important role in coping with the dynamic nature of these environments. Elasticity mechanisms allow adding or retrieving application instances to deal with the changing number of incoming queries. Determining the optimal number of instances needed in a given horizon is really challenging, since we are dealing with a random number of incoming queries and given that the number of queries fulfilled by a single instance is random as well. Also, there is a trade-off between deploying too many instances and thus paying unnecessary deployment costs and deploying too few of them, and thus paying penalties for not being able to fulfill all in-coming queries on-time. In this paper, we propose a stochastic programming method that determines the optimal number of instances needed in a given planning horizon, putting in mind the uncertain parameters of the problem. In our approach, we learn from the historical behavior of the system to predict the probability distributions of the unknown data, and then formulate a stochastic programming model that optimizes the aforementioned trade-off and outputs the optimal provisioning plan.