This paper proposes an innovative multi-period modeling approach to solve the airline fleet planning problem under demand uncertainty. The problem is modeled using a scenario tree approach. The tree is composed of nodes, which represent points of decision in multiple time stages of the planning horizon, and branches, representing demand variation scenarios. The branches link the decision nodes in consequent time stages and compose scenario paths. Fleet decisions are modeled according to these scenario paths, resembling the real-life process in which fleet plans are not defined in a single moment but instead are adjusted according to the demand development. Given that some scenario paths share common decision nodes, decisions among scenarios need to be synchronized. A mixed-integer linear programming model is proposed to determine the ideal fleet composition for each scenario in the tree and to describe this interdependency between scenarios. Given the probability of a scenario, fleet composition probabilities for each time-period can be determined. Two real-world based case studies are performed to show the validity of the model. Results show that the proposed scenario tree approach can provide flexible multi-period airline fleet plans, which are more robust to future demand scenarios than fleet solutions obtained using the traditional approach of considering a single deterministic demand evolution scenario.