Airlines operate their fleet of aircraft over a relatively long time horizon during which the realized stochastic demand has the potential to profoundly impact the airlines’ financial performance. This makes the investment in a fleet of aircraft a highly capital-intensive long-term commitment, associated with inherent risks. We propose an innovative three-step airline fleet planning methodology with the primary objective of identifying fleets that are robust to stochastic demand realizations. The methodology presents two main innovation aspects. The first one is the use of the mean reverting Ornstein–Uhlenbeck process to model the long-term travel demand, which is then combined with discrete-time Markov chain transitions to generate demand scenarios. The second innovative aspect is the adoption of a portfolio-based fleet planning perspective that allows for an explicit comparison of different fleets, in size and composition. Ultimately, the methodology yields for each fleet in the portfolio a distribution of net present values of operating profit across the planning horizon and a list of key financial and operational metrics per year. The robustest fleet can be selected based on the operating profit generating capability across different realizations of stochastic demand. An illustrative case study is presented as a proof of concept. The case study is used to demonstrate the type of results obtained and to discuss the usefulness of the methodology proposed.