The unexpected aircraft failure is one of the main disruption factors that cause flight irregularity. The aircraft schedule recovery is a challenging problem in both industrial and academic fields, especially when aircraft restoration time is uncertain, which is often ignored in previous research. This paper established a two-stage stochastic recovery model to deal with the problem. The first stage model was a resource assignment model on aircraft schedule recovery, with the objective function of minimizing delay and cancellation cost. The second stage model used simple retiming strategy to adjust the aircraft routings obtained in the first stage, with the objective function of minimizing the expected cost on recourse decision. Based on different scenarios of restoration time, the second stage model can be degenerated as several linear models. A stochastic Greedy Simulated Annealing algorithm was designed to solve the model. The computational results indicate that the proposed stochastic model and algorithm can effectively improve the feasibility of the recovery solutions, and the analysis of value of stochastic solution shows that the stochastic model is worthy of implementation in real life.