Given a flight schedule and a set of aircraft of different types, the airline fleet assignment problem (FAP) consists of assigning an aircraft type to each flight with the objective of maximizing the expected profits. Typically, the expected revenues are computed using the average demand for each potential passenger itinerary (this case is referred to as the FAP with deterministic demand). In this paper, we assume that the demand is stochastic and we address the FAP with stochastic demand. We propose a two-stage stochastic optimization model with recourse where an initial fleet assignment is implemented in the first stage and re-fleeting of pre-defined flight leg sequences can be performed in the second stage to face deviations from the average demand. Demand stochasticity is modeled using a limited set of demand scenarios. Computational results obtained on instances derived from a real-world flight network involving up to 5,180 flight legs show that the resulting model can be solved by a commercial mixed integer programming solver in reasonable computational times (up to an average of 12 hours) and that the computed solutions can yield significant additional expected profits compared to those derived from the solutions of the FAP with deterministic demand.