In the electricity market environment, joint bidding of energy storage and wind power can deal with the uncertainty of wind power output and improve the comprehensive benefit of the wind power enterprise. In this paper, the model and algorithm of joint bidding of wind power and compressed air energy storage are studied. Firstly, by considering the operation characteristics of wind power and compressed air energy storage and the rules of electricity market, a bidding model for wind power and compressed air energy storage to participate in the energy market and frequency regulation market is established. Secondly, the proposed model is described as a multi-stage stochastic programming problem in the framework of Markov decision process, and then solved based on the stochastic dual dynamic integer programming algorithm. The algorithm realizes the period decomposition of the proposed model through Lagrange cut, which can effectively solve the problems of randomness and discreteness, and has high solving accuracy. Finally, case studies verify the effectiveness of the proposed method.