This paper introduces a new two-stage stochastic optimisation approach for the strategic airline crew planning problem with uncertain demand. The developed model provides the airline with a cockpit crew composition plan per crew position before the flight schedule and crew demand are known. This is done by estimating future crew demand and by treating it as a stochastic variable. Historical crew demand is analysed and is assumed to follow a Beta probability distribution. Since demand at different crew positions is correlated, demand scenarios are generated from these distributions by using Latin hypercube sampling (LHS) for correlated variables. The generated scenarios are multiplied with a trend value to account for a predicted demand increase or decrease. In the first stage, the model determines the number of permanent employees, while in the second stage we consider hiring temporary crew members, the transition of crew members between compatible positions and the option to fire permanent crew members. This second stage comes with a recourse cost. Three case studies are performed for a holiday airline with both scheduled and charter flights to validate the model and test its possibilities. Results show that the model provides a cost reduction of 2.1% with respect to the airline’s current practice and a further 4.5% when affluent crew members can be fired. Results also show that the model is adjustable to assist the airline with its strategic crew plan in the post-Covid-19 recovery phase. Furthermore, it is concluded that the model is flexible and that it can handle demand fluctuations.