Aiming at the cloud resource provisioning problem, a stochastic programming based cloud resource allocation algorithm is proposed to reduce the total resource provisioning cost of the service provider. Combining the reservation plan and the on-demand plan, the cloud resource provisioning problem can be formulated as a two-stage stochastic programming problem using the probability distribution of the workload demand. Then the sample average approximation approach and a stage decomposition based hybrid evolutionary algorithm are applied to solve the cloud resource provisioning problem. The simulation results show that the proposed cloud resource allocation algorithm can obtain near optimal resource reservation scheme within a short time, reducing the total resource provisioning cost of the service provider significantly.