In this paper, we study a strategic fleet planning problem faced by TAP, the Portuguese legacy carrier. The study is intended to shed light on the aircraft models to select, as well as on the mix of aircraft to purchase (or financially lease) and the aircraft to operationally lease in order to cope with the forecasted passenger demand between Lisbon and Brazil in the year 2020. The approach we developed for addressing this problem is based on an optimization model that can be cast in the class of two-stage stochastic integer programs. In our opinion, the proposed approach can be a valuable alternative or complement to the methods currently used in practice. The results of the study provide clear insights on how TAP should renovate its fleet, obviously depending on the available resources. The leasing of aircraft is an option that should definitely be taken into consideration by TAP, since it allows the carrier to deal with demand uncertainty without investing large amount of resources in the purchase of new aircraft.