In this paper, a stochastic electricity market model is applied to estimate the effects of significant wind power generation on system operation and on economic value of investments in compressed air energy storage (CAES). The model's principle is cost minimization by determining the system costs mainly as a function of available generation and transmission capacities, primary energy prices, plant characteristics, and electricity demand. To obtain appropriate estimates, notably reduced efficiencies at part load, start-up costs, and reserve power requirements are taken into account. The latter are endogenously modeled by applying a probabilistic method. The intermittency of wind is covered by a stochastic recombining tree and the system is considered to adapt on increasing wind integration over time by endogenous modeling of investments in selected thermal power plants and CAES. Results for a German case study indicate that CAES can be economic in the case of large-scale wind power deployment.