The Aircraft Recovery Problem appears when external events cause disruptions in a flight schedule. Thus in order to minimize the losses caused by the externalities, aircrafts must be reallocated (rescheduled) in the best possible way. The aim of this paper is to develop a suitable methodology that combines optimization techniques with a simulation approach to tackle the so-called Stochastic Aircraft Recovery Problem. The approach solves the problem through the rescheduling of the flight plan using delays, swaps, and cancellations. The main objective of the optimization model is to restore as much as possible the original flight schedule, minimizing the total delay and the number of cancelled flights. By applying simulation techniques, the robustness of the given solution is assessed. The proposed methodology is applied on a medium-sized scenario based on real data provided by a commercial airline. The obtained results show that the methodology described in the paper is capable of producing a feasible and robust solution for this problem.